{"thread":{"id":"38905","subject":"[RFC/GSoC] Proposal: Make git-pull and git-am builtins","startedAt":"2015-03-24T16:37:30Z","lastAt":"2015-03-26T05:02:54Z","messageCount":9,"participants":["Paul Tan","Matthieu Moy","Junio C Hamano","Sebastian Schuberth"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"258420","messageId":"20150324163730.GA8366@yoshi.chippynet.com","threadId":"38905","inReplyTo":null,"subject":"[RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Paul Tan","fromEmail":"pyokagan@gmail.com","sentAt":"2015-03-24T16:37:30Z","receivedAt":"2015-03-24T16:37:30Z","isPatch":false,"sender":{"key":"pyokagan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/109479?v=4"},"body":"Hi all,\n\nI'm applying for git in the Google Summer of Code this year. For my\nproject, I propose to rewrite git-pull.sh and git-am.sh into fast\noptimized C builtins. I've already hacked up a prototype of a builtin\ngit-pull in [1], and it showed a promising 8x improvement in execution\ntime on Windows.\n\nBelow is the full text of the proposal as submitted to google-melange\nfor your review and feedback. It is marked up in reStructuredText. The\nlatest (and rendered) version can be found at [2].\n\nRegards,\nPaul.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/265628\n[2] https://gist.github.com/pyokagan/1b7b0d1f4dab6ba3cef1\n\n(Thanks Matthieu for suggesting to post this on the mailing list. Will\nreply to your comments in a separate email).\n\n-->8--\n\n========================================\nMake `git-pull` and `git-am` builtins\n========================================\n\n:Abstract: `git-pull` and `git-am` are frequently used git subcommands.\n           However, they are porcelain commands and implemented as shell\n           scripts, which has some limitations which can cause poor\n           performance, especially in non-POSIX environments like Windows.\n           I propose to rewrite these scripts into low level C code and make\n           them builtins.  This will increase git's portability, and may\n           improve the efficiency and performance of these commands.\n\n.. section-numbering::\n\nLimitations of shell scripts\n=============================\n\n`git-pull` is a commonly executed command to check for new changes in the\nupstream repository and, if there are, fetch and integrate them into the\ncurrent branch. `git-am` is another commonly executed command for applying a\nseries of patches from a mailbox to the current branch. They are both git\nporcelain commands -- with no access to git's low level internal API.\nCurrently, they are implemented by the shell scripts ``git-pull.sh`` and\n``git-am.sh`` respectively. These shell scripts require a fully-functioning\nPOSIX shell and utilities. As a result, these commands are difficult to port to\nnon-POSIX environments like Windows.\n\nSince porcelain commands do not have access to git's internal API, performing\nany git-related function, no matter how trivial, requires git to be spawned in\na separate process. This limitation leads to these git commands being\nrelatively inefficient, and can cause long run times on certain platforms that\ndo not have copy-on-write ``fork()`` semantics.\n\nSpawning processes can be slow\n-------------------------------\n\nShell scripting, by itself, is severely limited in what it can do.\nPerforming most operations in shell scripts require external executables to be\ncalled. For example, ``git-pull.sh`` spawns the git executable not only to\nperform git operations like `git-fetch` and `git-merge`, but it also spawns the\ngit executable for trivial tasks such as retrieving configuration values with\n`git-config` and even quoting of command-line arguments with ``git rev-parse\n--sq-quote``. As a result, these shell scripts usually end up spawning a lot of\nprocesses.\n\nProcess spawning is usually implemented as a ``fork()`` followed by an\n``exec()`` by shells. This can be slow on systems that do not support\ncopy-on-write semantics for ``fork()``, and thus needs to duplicate the memory\nof the parent process for every ``fork()`` call -- an expensive process.\n\nFurthermore, starting up processes on Windows is generally expensive as it\nperforms `several extra steps`_ such as such as using an inter-process call to\nnotify the Windows Client/Server Runtime Subsystem(CSRSS) about the process\ncreation and checking for App Compatibility requirements.\n\n.. _`several extra steps`:\n    http://www.microsoft.com/mspress/books/sampchap/4354a.aspx\n\nThe official Windows port of git, Git for Windows, uses MSYS2 [#]_ to emulate\n``fork()``. Since Windows does not support forking semantics natively, MSYS2\ncan only emulate ``fork()`` `without copy-on-write semantics`_. Coupled with\nWindows heavy process creation, this causes huge slowdowns of git on Windows.\n\n.. _`without copy-on-write semantics`:\n    https://www.cygwin.com/faq.html#faq.api.fork\n\nA \"no-updates\" `git-pull`, for example, takes an average of 5.1s [#]_, as\ncompared to Linux which only takes an average of 0.08s. 5 seconds,\nwhile seemingly short, would seem like an eternity to a user who just wants to\nquickly fetch and merge changes from upstream.\n\n`git-am`'s implementation reads each patch from the mailbox in a while loop,\nspawning many processes for each patch. Considering the cost of spawning each\nprocess, as well as the fact that runtime grows linearly with the number of\npatches, git-am takes a long time to process a seemingly small number of\npatches on Windows as compared to Linux. A quick benchmarks shows that `git-am`\ntakes 7m 20.39s to apply 100 patches on Windows, compared to Linux, which took\nonly 0.08s.\n\nCommands which call `git-am` are also affected as well. ``git-rebase--am.sh``,\nwhich implements the default, patch-based, non-interactive rebase of the\n`git-rebase` command, is implemented by first calling `git-format-patch` (a C\nbuiltin) to generate the patches of commits to be rebased, and then applying\nthe commits on top of the new head using git-am. On Windows, the execution time\nof `git-am` currently takes up around 98% of `git-rebase`'s execution time for\nnon-interactive rebases [#]_. If `git-am` was made to perform faster,\n`git-rebase` would benefit greatly.\n\n.. [#] The current Git for Windows is based on MSYS, but shares many of the\n    limitations of MSYS2 as they are both derived from cygwin. This proposal is\n    written with MSYS2 in mind, as Git For Windows will use it in the future.\n\n.. [#] The `git-pull` from a local remote with no updates. As a benchmark,\n    `git-pull` was run with this setup 100 times on Windows and Linux boxes\n    with similar specs. `git-pull` was executed from a native process on\n    Windows to avoid MSYS2's forking overhead.\n\n.. [#] git-rebase was used to rebase 100 commits in non-interactive mode\n    with ``GIT_TRACE`` on. The timings were taken from the resulting output and\n    matched up with the code in ``git-am.sh`` and ``git-rebase--am.sh``. The\n    total execution time was 8m 0s, of which `git-format-patch` took only 0.5s,\n    but `git-am` took 7m 52s.\n\nScripting languages introduce more dependencies\n-------------------------------------------------\n\nScripting languages, while allowing for faster prototyping of commands,\nintroduce dependencies into the git distribution. The problem is greater with\nshell scripts which, due to their simple nature, need to call other executables\nto perform non-trivial tasks. `git-pull` and `git-am` combined requires `test`,\n`printf`, `echo`, `sed`, `tr`, `grep`, `cat`, `mkdir`, `rm`, `mv`, `perl` etc.\nThese may seem like common POSIX utilities, but when porting git to non-POSIX\nplatforms, these commands must all be ported and installed on the system in its\nentirety. Git for Windows, for example, requires around 250MB of disk space for\nits installation as it includes the MSYS2 shell and utilities, as well as\nlanguage runtimes for Perl and Tcl/Tk.\n\nFurthermore, should any workarounds be required to support the platform, it\nmust be implemented in all of these dependency libraries and executables. Git,\nfor example, implements a compatibility function for ``unlink()`` on Windows\nthat deals with failures that can occur if another process has an open handle\non the file [#]_. However, this only helps git builtins, and will have to be\nimplemented again on all the other dependency shell utilities. Thus, shell\nscripts do not benefit from this compatibility function, and will have to\nworkaround file deletion failures separately, leading to lots of duplicated\ncode.\n\n.. [#] See ``mingw_unlink()`` in ``compat/mingw.c``.\n\nScripts have inefficiencies\n----------------------------\n\nAs stated above, porcelain do not have access to the git internal API, and\nthus have to spawn git processes in order to perform any git-related operation,\nno matter how trivial it is. In every git invocation, git would have to re-read\nthe user's configuration files, repository index, repopulate the filesystem\ncache (for Windows) etc. This leads to a lot of unnecessary IO, which on\noperating systems with poor file system performance (i.e. Windows) will lead to\nruntime overhead as well.\n\nGit has internal caches for configuration values, the repository index and\nrepository objects. By rewriting the porcelain into C builtins and using the\ngit internal API instead of spawning separate git processes, these caches can\nbe taken advantage of to reduce redundant IO accesses.\n\nRewriting shell scripts to C\n=============================\n\nIn order to eliminate the aforementioned portability and performance\nlimitations, I propose that these scripts be rewritten into C builtins. The C\nprogramming language provides a richer set of data types, and also provides\naccess to git's internal API. Thus, the above problems can be solved:\n\n* git is a native executable on Windows, and thus does not require MSYS2 POSIX\n  emulation. Spawning processes will not incur the overhead of MSYS2 fork\n  emulation.\n\n* Converting shell scripts into builtins will reduce the git distribution's\n  dependence on other software. In the future, if all core git functionality is\n  converted into C, it would greatly ease porting of git to platforms which\n  only require the core subset of git's functionality.\n\n* Taking advantage of git's internal API and C data types can remove the\n  inefficiencies inherent in shell scripts. For example, instead of spawning a\n  `git-config` process to get a configuration value, ``git_config_get_value()``\n  can be used. This function also takes advantage of git's configuration cache,\n  which means that configuration files only need to be read once to access all\n  of the configuration values, thus reducing IO.\n\nIn addition, `git-pull` and `git-am`'s behavior can also become more consistent\nwith other git builtin through the git internal API. Currently, command line\narguments in `git-pull` and `git-am` are parsed manually with a while loop and\npattern matching. As a result, their command line interface is inconsistent\nwith other git builtins, which use the ``parse-options`` API. For example, in\n`git-pull` the option ``--st`` should thrown an ambiguous option error as it\ncould mean ``--stat`` or ``--strategy``, but ``git-pull.sh`` is hardcoded to\nassume ``--st`` resolves to ``--strategy``. `git-pull` and `git-am` also do not\nprovide usage information with the ``-h`` flag. Rewriting these commands to use\n``parse-options`` would make their command line interfaces consistent with\nother git builtins.\n\nIn order to fully take advantage of the above benefits of implementing\n`git-pull` and `git-am` in C, especially with regards to making the resulting C\ncode as efficient and fast as possible, I propose the following requirements\nfor the rewritten code:\n\n1. No spawning of external git processes. This is to support systems with high\n   ``fork()`` or process creation overhead, and to reduce redundant IO by\n   taking advantage of the internal object, index and configuration cache.\n\n2. Avoid needless parsing/string conversions by directly accessing the C data\n   structures. Massaging of strings cause too much code churn, so functions\n   that take the richer C data types as input should be preferred over\n   functions that work by parsing string arguments.\n\nOverall, rewriting git-pull and git-am into efficient C code will most likely\nlead to impressive speedups on platforms most affected by the aforementioned\nlimitations like Windows. The `prototype rewrite of git-pull`_, for example,\ntakes only an average of 0.63s on the same \"no-updates\" benchmark. Compared to\nthe shell script which took an average of 5.1s, this is nearly an 8x\nimprovement in execution time.\n\n.. _`prototype rewrite of git-pull`:\n    http://thread.gmane.org/gmane.comp.version-control.git/265628\n\nOn the other hand, the rewritten code should not cause regressions in the\ncommand as compared to the original scripts as the time wasted on dealing with\nthe bugs may outweigh any advantages of rewriting these scripts, especially on\nplatforms which do not suffer so much from the limitations of scripts like\nLinux. Therefore, I propose the following additional requirements:\n\n3. The resulting builtin should not have wildly different behavior or bugs\n   compared to the shell script.\n\n4. The rewritten code should not be much harder to maintain than the original\n   script.\n\nThese requirements leads to some potential difficulties in rewriting `git-pull`\nand `git-am`.\n\nPotential difficulties\n=======================\n\nRewriting code may introduce bugs\n----------------------------------\n\nA dangerous possibility of rewriting code is that bugs may be introduced into\nthe rewritten version without detection. The test suite can help in catching\nsome bugs, however there is still the possibility that the test suite may not\nbe comprehensive enough. Generally, the ideal method of catching errors and\nbugs is through careful rewriting and review of the code. However, such reviews\nwould require a lot of time and effort. In order to ensure that the rewrite can\nbe completed during the GSoC period, it would be useful if the test suite could\nprovide some sort of guarantee that the rewritten code *most probably* did not\nintroduce any bugs. For this purpose, code coverage tools can be used to ensure\nthat the test suite for the command tests all major code paths in the rewritten\nbuilt-in.\n\nWe can also avoid introducing logical errors by following the logical structure\nof the original script in the rewritten code.  This means largely doing a\nline-by-line, one-to-one translation of the shell script into C. For instance,\nthis line in ``git-pull.sh`` calls `git-merge-base` to calculate the point in\nhistory in which ``$curr_branch``, the current branch, forked from the upstream\nremote tracking branch, ``$remoteref``::\n\n    oldremoteref=$(git merge-base --fork-point \"$remoteref\" $curr_branch 2>/dev/null)\n\nAssuming ``remoteref`` and ``curr_branch`` are strings, the equivalent C code,\nusing the ``run-command`` API, would look like::\n\n    struct child_process cmd = CHILD_PROCESS_INIT;\n    struct strbuf oldremoteref = STRBUF_INIT;\n    argv_array_pushl(&cmd.args, \"merge-base\", \"--fork-point\", remoteref, curr_branch, NULL);\n    cmd.out = -1;\n    cmd.no_stderr = 1;\n    cmd.git_cmd = 1;\n    if (!start_command(&cmd)) {\n        strbuf_read(&oldremoteref, cmd.out, 0);\n        close(cmd.out);\n        finish_command(&cmd);\n    }\n\nOf course, the downside of following this too strictly is that if there were\nany logical bugs in the original code, or if the original code is unclear, the\nrewritten code would inherit these problems too. For example, the code in\n``git-pull.sh`` assumes in certain code paths that the repository and refspecs\nto fetch are the only arguments present in ``\"$@\"``. However, the ``\"$@\"``\nautomatic variable would also contain the command-line options to be passed to\n`git-fetch` as well [#]_. The rewritten `git-pull` should, for the purpose of\nmaking code maintenance easy, fix these logical errors.\n\n.. [#] An example of such an assumption can be found in\n    ``remoteref=\"$(get_remote_merge_branch \"$@\" 2>/dev/null)\"``.\n    ``get_remote_merge_branch`` assumes that the first argument is the remote\n    name, and will thus fail (silently) if it ends up being arguments for\n    git-fetch.\n\nRewritten code may become harder to understand\n-----------------------------------------------\n\nFor the purpose of reducing git's dependencies, the rewritten C code should not\ndepend on other libraries or executables other than what is already available\nto git builtins. However, C is a much more verbose language than shell script,\nand does not provide much advanced facilities for processing text.  As a\nresult, text processing functions in shell scripts can end up as huge\nmulti-line functions in C. For instance, in ``git-pull.sh``, by relying on\n`sed` and `tr`, all heads valid for merge from ``FETCH_HEAD`` can be retrieved\nwith a single short-and-succinct pipeline::\n\n    merge_head=$(sed -e '/\tnot-for-merge\t/d' \\\n        -e 's/\t.*//' \"$GIT_DIR\"/FETCH_HEAD | \\\n        tr '\\012' ' ')\n\nA strict translation of the pipeline to C becomes something like::\n\n    struct strbuf merge_head = STRBUF_INIT;\n    FILE *fp = fopen(git_path(\"FETCH_HEAD\"), \"r\");\n    for (;;) {\n        char sha1_text[40];\n        char text[128];\n        int c, ret;\n\n        ret = fscanf(fp, \"%40c %127[^\\n]\", sha1_text, text);\n        if (ret == EOF)\n            break;\n        else if (ret != 2)\n            die(_(\"error parsing %s\"), filename);\n        for (;;) {\n            c = fgetc(fp);\n            if (c == '\\n' || c == EOF)\n                break;\n        }\n        if (strstr(text, \"not-for-merge\"))\n            continue;\n        strbuf_addstr(merge_head, sha1_text);\n        strbuf_addstr(merge_head, \" \");\n    }\n    fclose(fp);\n\nWe can see that the C version requires much more lines compared to the shell\npipeline, which will contributes to the \"bloating\" of the C code. It may even\nseem to be more cryptic. This is a known trade-off of the C programming\nlanguage, and not depending on external libraries and dependencies. The best\nsolution is to improve the design of the rewritten code. For example, the above\ncan be moved into an appropriately-named function. The function can then be\ndocumented with well-defined inputs, outputs, and behavior. This should help\nthe resultant code to be much more understandable.\n\nDevelopment approach and deliverables\n======================================\n\nIn the first stage (and throughout the course of the project), test suite code\ncoverage for each command is reviewed using `kcov`_ [#]_. At the minimum, the\ntest suite should cover the major code paths and command-line switches of the\nscript. These tests do not necessarily have to be perfect or comprehensive\nbefore the next stage can begin (in fact they would most likely proceed in\nparallel), however the minimum required tests must be identified and written in\norder to give a good idea of what needs to be tested, and provides a safety net\nfor the later stages. Tests will be kept in a separate patch queue as they are\napplicable whether `git-pull` and `git-am` are builtins or not. By the end\nof the project, the test suite for `git-pull` and `git-am` will be more\ncomprehensive.\n\n.. _kcov: http://simonkagstrom.github.io/kcov/\n\nIn the second stage, the shell scripts are translated line-by-line into their\ncorresponding C code. The translation should not be overly strict -- where\nappropriate the corresponding git internal API functionality can be used\ninstead. For example, in `git-pull` and `git-am` the ``parse-options`` API can\nbe used instead of manually implementing command-line argument parsing like how\nthe shell scripts currently do. If the shell script has any obvious bugs or\nerrors (perhaps identified in the first stage), they should be fixed in this\nstage as well. The resultant C code at the end of this stage may not\nnecessarily be efficient, but it should be functionally complete and error\nfree to serve as a baseline product for the final stage. The final product\nwould most probably look something like the `prototype rewrite of git-pull`_,\nbut with more usage of the run-command APIs and without the bugs.\n\n.. _`prototype rewrite of git-pull`:\n    http://thread.gmane.org/gmane.comp.version-control.git/265628\n\nIn the final stage, the baseline C code will be optimized for speed and\nefficiency. For prioritization of efforts, the baseline builtins will be\nprofiled using their respective test suites in order to find hotspots.\nThe builtins will also be benchmarked to compare their performance\nwith the original shell scripts. Since `git-pull` is just a simple wrapper\naround `git-fetch`, `git-merge` and `git-rebase`, the benchmark will simply\nconcentrate on run time for common use cases. (e.g. the \"no updates\" use case).\nFor `git-am`, the benchmark can rely on its performance when applying a large\nnumber of patches (e.g. a `patchbomb benchmark`_).\n\n.. _`patchbomb benchmark`:\n    http://thread.gmane.org/gmane.comp.version-control.git/1681/focus=2369\n\nShould there be no hotspots found, general optimization will be done to reduce\noverheads. ``run-command`` API calls will be replaced with the relevant\ncorresponding git internal API calls. Strings will be replaced with their\ncorresponding git C data types where possible to avoid needless string\nconversions. For example, SHA1s will be parsed once and stored in ``unsigned\nchar[20]`` or ``sha1_array`` data types. Some refactoring may also be required.\nFor example, for `git-pull` to access ``git-merge-base --fork-point``\nfunctionality without spawning a separate process, the function\n``handle_fork_point()`` in ``builtin/merge-base.c`` must be made available. The\nfunction must also be modified to not call ``die()`` on errors.\n\n.. [#] An example kcov code coverage report for the git-pull tests can be found\n    `here`_\n\n.. _here: https://83dc3588620c5a97164396ec753a2fa480f6a7b0-www.googledrive.com/host/0B4O2AiYulllpfmJlTW4xT050OVVicnNWWS02dm52aTJ2TFIwQ2QwdWh0VHotSkU4eUNNWjg/git-pull/git-pull.360f32c2.html\n\nTimeline\n=========\n\nUnfortunately, my university term begins on the 3rd of August. On the other\nhand, though, I am currently not attending university so I'm effectively free\nbefore the Summer holidays even begin. As such, to compensate, I will begin\ncoding right after accepted student proposals are announced so that the period\nfor coding is still 3 months.\n\nThe timeline is as follows:\n\n* Apr 27: Accepted student proposals announced.\n\n* Apr 27: Stage 1 begins: Review of test suite coverage.\n\n* Apr 27 onwards: Discussion of any bugs or behavior in `git-am` and\n  `git-pull` that should be fixed or changed. This will continue throughout the\n  project.\n\n* May 4: Stage 2 (Baseline rewrite) begins in parallel\n\n* May 4 - May 17 (2 weeks): Full baseline rewrite of ``git-am.sh``.\n\n* May 18: 1st version of ``builtin/am.c`` published on mailing list for review.\n\n* May 18 - May 24 (1 week): Full baseline rewrite of ``git-pull.sh``.\n\n* May 25: 1st version of ``builtin/pull.c`` published on mailing list for\n  review.\n\n* May 25 - Jun 22 (5 weeks): ``builtin/am.c`` and ``builtin/pull.c`` are\n  iterated on in an alternating fashion to pass code review.\n\n* Jun 22: Stage 3 (Optimization) begins\n\n* Jun 22 - Jun 24: Benchmarking and profiling is done on the new builtins,\n  especially as compared to their original shell scripts, to check for any\n  performance improvements and to guide optimization. These results are\n  published to mailing list and discussed.\n\n* Jun 24 - Jul 19 (3.5 weeks): Stage 3 (Optimization). ``builtin/am.c`` and\n  ``builtin/pull.c`` are iterated on in an alternating fashion to pass code\n  review.\n\n* Jul 3: Mid-term evaluations deadline\n\n* Jul 20 - Aug 2 (2 weeks): Pencils down -- focus on polishing up\n  ``builtin/am.c``, ``builtin/pull.c`` and the tests patch series.\n\n* Aug 17: Suggested 'pencils-down' date.\n\n* Aug 21: Firm 'pencils-down' date.\n\n* Aug 28: Final evaluation deadline\n\nAbout me\n=========\n\nI've been accepted to the `National University of Singapore`_ for a bachelors\nin Computer Engineering, and will matriculate on 3rd August 2015. I've been\nwriting Python, C and C++ for around 4 years, and some of my experiments can be\nfound on my `github profile`_. I have also contributed patches successfully to\n`libuv`_ and `node-contextify`_.\n\nMy microproject is to implement ``XDG_CONFIG_HOME support`` in\ngit-credential-store. Patch series: `v5`_, `v4`_, `v3`_, `v2`_, `v1`_.\n\n.. _`National University of Singapore`: http://www.ceg.nus.edu.sg/\n\n.. _`github profile`: https://github.com/pyokagan\n\n.. _`libuv`: https://github.com/joyent/libuv/commit/347000929de775ae6b975a2959f5fabe81d6f1f0\n\n.. _`node-contextify`: https://github.com/brianmcd/contextify/commit/7e3e0a89779cd892b3d8604795b6675d6aecff17\n\n.. _v1: http://thread.gmane.org/gmane.comp.version-control.git/264682\n\n.. _v2: http://thread.gmane.org/gmane.comp.version-control.git/265042\n\n.. _v3: http://thread.gmane.org/gmane.comp.version-control.git/265305\n\n.. _v4: http://thread.gmane.org/gmane.comp.version-control.git/265683\n\n.. _v5: http://thread.gmane.org/gmane.comp.version-control.git/266175\n"},{"id":"258426","messageId":"CACRoPnRBBVGt8PVHVEYct46abLMJvKf0+MNz7bX2nx2C7OHd3Q@mail.gmail.com","threadId":"38905","inReplyTo":"20150324163730.GA8366@yoshi.chippynet.com","subject":"Re: [RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Paul Tan","fromEmail":"pyokagan@gmail.com","sentAt":"2015-03-24T17:22:08Z","receivedAt":"2015-03-24T17:22:08Z","isPatch":false,"sender":{"key":"pyokagan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/109479?v=4"},"body":"On Tue, Mar 24, 2015 at 6:19 PM, Matthieu Moy\n<Matthieu.Moy@grenoble-inp.fr> wrote:\n> A few minor details:\n>\n> \"on operating systems with poor file system performance (i.e. Windows)\"\n> => that's not only windows, I also commonly use a slow filesystem on\n> Linux, just because it's NFS. Mentionning other cases of poor filesystem\n> performance would show that the benefit is not limited to windows users,\n> and would give less of a taste of \"windows-bashing\".\n\nAh right, I didn't think of network file systems. Thanks for the suggestion.\n\n> About the timeline: I'd avoid too much parallelism. Usually, it's best\n> to try to send a first patch to the mailing list as soon as possible,\n> hence focus on one point first (I'd do that with pull, since that's the\n> one which is already started). Then, you can parallelize coding on git\n> am and the discussion on the pull patches. Whatever you plan, review and\n> polishing takes more than that ;-). The risk is to end up with an almost\n> good but not good enough to be mergeable code. That said, your timeline\n> does plan patches and review early, so I'm not too worried.\n>\n\nWell, I was thinking that after the full rewrite (2nd stage, halfway\nthrough the project), any optimizations made to the code will be done\niteratively (and in separate small patches) so as to keep the patch\nseries in an \"always almost mergeable\" state. This will hopefully make\nit much easier and shorter to do any final polishing and review for\nmerging.\n\n> A general advice: if time allows, try to contribute to discussions and\n> review other than your own patches. It's nice to feel integrated in the\n> community and not \"the GSoC student working alone at home\" ;-).\n\nYeah I apologize for not participating in the list so actively because\nwriting the git-pull prototype and the proposal took a fair chunk of\nmy time. Also, my expertise with the code base is not that great yet\nso it takes quite a bit more effort for me to contribute\nconstructively, but I expect that will improve in the future. Now that\nthe proposal is more or less complete I can spend more time on\ndiscussions.\n\nThanks,\nPaul\n"},{"id":"258427","messageId":"vpq4mpas3nk.fsf@anie.imag.fr","threadId":"38905","inReplyTo":"CACRoPnRBBVGt8PVHVEYct46abLMJvKf0+MNz7bX2nx2C7OHd3Q@mail.gmail.com","subject":"Re: [RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2015-03-24T17:31:43Z","receivedAt":"2015-03-24T17:31:43Z","isPatch":false,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Paul Tan <pyokagan@gmail.com> writes:\n\n> On Tue, Mar 24, 2015 at 6:19 PM, Matthieu Moy\n> <Matthieu.Moy@grenoble-inp.fr> wrote:\n>\n>> About the timeline: I'd avoid too much parallelism. Usually, it's best\n>> to try to send a first patch to the mailing list as soon as possible,\n>> hence focus on one point first (I'd do that with pull, since that's the\n>> one which is already started). Then, you can parallelize coding on git\n>> am and the discussion on the pull patches. Whatever you plan, review and\n>> polishing takes more than that ;-). The risk is to end up with an almost\n>> good but not good enough to be mergeable code. That said, your timeline\n>> does plan patches and review early, so I'm not too worried.\n>>\n>\n> Well, I was thinking that after the full rewrite (2nd stage, halfway\n> through the project), any optimizations made to the code will be done\n> iteratively (and in separate small patches)\n\nYes, that's why I'm not too worried. But being able to say \"this part is\ndone, it won't disturb me anymore\" ASAP is still good IMHO, even if\n\"this part\" is not so big.\n\nBut again, I'm thinking out loudly, feel free to ignore.\n\n>> A general advice: if time allows, try to contribute to discussions and\n>> review other than your own patches. It's nice to feel integrated in the\n>> community and not \"the GSoC student working alone at home\" ;-).\n>\n> Yeah I apologize for not participating in the list so actively because\n> writing the git-pull prototype and the proposal took a fair chunk of\n> my time.\n\nDon't apologize, you're doing great. I'm only pointing out things that\ncould be \"even better\", but certainly not blaming you!\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"258441","messageId":"xmqqwq265jjl.fsf@gitster.dls.corp.google.com","threadId":"38905","inReplyTo":"20150324163730.GA8366@yoshi.chippynet.com","subject":"Re: [RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-24T18:37:02Z","receivedAt":"2015-03-24T18:37:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Paul Tan <pyokagan@gmail.com> writes:\n\n> ..., I propose the following requirements for the rewritten code:\n>\n> 1. No spawning of external git processes. This is to support systems with high\n>    ``fork()`` or process creation overhead, and to reduce redundant IO by\n>    taking advantage of the internal object, index and configuration cache.\n\nI suspect this may probably be too strict in practice.\n\nTrue, we should never say \"run_command_capture()\" just to to read\nfrom \"git rev-parse\"---we should just call get_sha1() instead.\n\nBut for a complex command whose execution itself far outweighs the\ncost of forking, I do not think it is fair to say your project\nfailed if you chose to run_command() it.  For example, it may be\nperfectly OK to invoke \"git merge\" via run_command().\n\n> 3. The resulting builtin should not have wildly different behavior or bugs\n>    compared to the shell script.\n\nThis on the other hand is way too loose.\n\nThe original and the port must behave identically, unless the\ndifference is fixing bugs in the original.\n\n> Potential difficulties\n> =======================\n>\n> Rewriting code may introduce bugs\n> ...\n\nYes, but that is a reasonable risk you need to manage to gain the\nbenefit from this project.\n\n> Of course, the downside of following this too strictly is that if there were\n> any logical bugs in the original code, or if the original code is unclear, the\n> rewritten code would inherit these problems too.\n\nI'd repeat my comment on the 3. above.  Identifying and fixing bugs\nis great, but otherwise don't worry about this too much.\n\nBeing bug-to-bug compatible with the original is way better than\nintroducing new bugs of an unknown nature.\n\n> Rewritten code may become harder to understand\n> ...\n\nAnd also it may become harder to modify.\n\nThat is the largest problem with any rewrite, and we should spend\nthe most effort to avoid it.\n\nA new bugs introduced we can later fix as long as the result is\nunderstandable and maintainable.\n\n> For the purpose of reducing git's dependencies, the rewritten C code should not\n> depend on other libraries or executables other than what is already available\n> to git builtins.\n\nPerhaps misphrased; see below.\n\n> We can see that the C version requires much more lines compared to the shell\n> pipeline,...\n\nThat is something you would solve by introducing reusable code in\nrun_command API, isn't it?  That is how various rewrites in the past\ndid, and this project should do so too.  You should aim to do this\nproject by not just using \"what is already available\", but adding\nwhat you discover is a useful reusable pattern into a set of new\nfunctions in the \"already available\" API set.\n"},{"id":"258484","messageId":"CACRoPnTL78ZrqPYYNPkNcW7vConHZXZ66z5P2=3HySrtmZKcrg@mail.gmail.com","threadId":"38905","inReplyTo":"xmqqwq265jjl.fsf@gitster.dls.corp.google.com","subject":"Re: [RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Paul Tan","fromEmail":"pyokagan@gmail.com","sentAt":"2015-03-25T05:55:22Z","receivedAt":"2015-03-25T05:55:22Z","isPatch":false,"sender":{"key":"pyokagan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/109479?v=4"},"body":"Hi,\n\nOn Wed, Mar 25, 2015 at 2:37 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Paul Tan <pyokagan@gmail.com> writes:\n>\n>> ..., I propose the following requirements for the rewritten code:\n>>\n>> 1. No spawning of external git processes. This is to support systems with high\n>>    ``fork()`` or process creation overhead, and to reduce redundant IO by\n>>    taking advantage of the internal object, index and configuration cache.\n>\n> I suspect this may probably be too strict in practice.\n>\n> True, we should never say \"run_command_capture()\" just to to read\n> from \"git rev-parse\"---we should just call get_sha1() instead.\n>\n> But for a complex command whose execution itself far outweighs the\n> cost of forking, I do not think it is fair to say your project\n> failed if you chose to run_command() it.  For example, it may be\n> perfectly OK to invoke \"git merge\" via run_command().\n\nYes, which is why I proposed writing a baseline using only the\nrun-command APIs first. Any other optimizations can then be done\nselectively after that.\n\nI think it's still good to have the ideal in mind though (and whoops I\nforgot to put in the word \"ideal\" in the text).\n\n>\n>> 3. The resulting builtin should not have wildly different behavior or bugs\n>>    compared to the shell script.\n>\n> This on the other hand is way too loose.\n>\n> The original and the port must behave identically, unless the\n> difference is fixing bugs in the original.\n>\n\nI was considering that there may be slight behavioral changes when the\nrewritten code is modified to take greater advantage of the internal\nAPI, especially since some builtins due to historical issues, may have\nduplicated code from the internal API[1].\n\n[1] I'm suspecting that the implementation of --merge-base in\nshow-branch.c re-implements get_octopus_merge_bases().\n\n>> Potential difficulties\n>> =======================\n>>\n>> Rewriting code may introduce bugs\n>> ...\n>\n> Yes, but that is a reasonable risk you need to manage to gain the\n> benefit from this project.\n>\n>> Of course, the downside of following this too strictly is that if there were\n>> any logical bugs in the original code, or if the original code is unclear, the\n>> rewritten code would inherit these problems too.\n>\n> I'd repeat my comment on the 3. above.  Identifying and fixing bugs\n> is great, but otherwise don't worry about this too much.\n>\n> Being bug-to-bug compatible with the original is way better than\n> introducing new bugs of an unknown nature.\n\nWell yes, but I was thinking that if there are any glaring errors in\nthe original source then it would be better to fix these errors during\nthe rewrite than wasting time writing code that replicates these\nerrors.\n\n>> Rewritten code may become harder to understand\n>> ...\n>\n> And also it may become harder to modify.\n>\n> That is the largest problem with any rewrite, and we should spend\n> the most effort to avoid it.\n>\n> A new bugs introduced we can later fix as long as the result is\n> understandable and maintainable.\n>\n>> For the purpose of reducing git's dependencies, the rewritten C code should not\n>> depend on other libraries or executables other than what is already available\n>> to git builtins.\n>\n> Perhaps misphrased; see below.\n\nIn this case I was thinking of \"making git depend on another project\".\n(e.g, using an external regular expression library). Of course a\nbalance has to be made in this aspect (thus the use of \"should not\"),\nbut git-pull and git-am are relatively simple so there should be no\nneed for that,\n\n>\n>> We can see that the C version requires much more lines compared to the shell\n>> pipeline,...\n>\n> That is something you would solve by introducing reusable code in\n> run_command API, isn't it?  That is how various rewrites in the past\n> did, and this project should do so too.  You should aim to do this\n> project by not just using \"what is already available\", but adding\n> what you discover is a useful reusable pattern into a set of new\n> functions in the \"already available\" API set.\n\nWhoops, forgot to mention that here. (A brief mention was made on this\nkind of refactoring in the Development Approach).\n\nThank you for your review.\n"},{"id":"258498","messageId":"20150325090720.GA19979@yoshi.chippynet.com","threadId":"38905","inReplyTo":"20150324163730.GA8366@yoshi.chippynet.com","subject":"[RFC/GSoC v2] Proposal: Make git-pull and git-am builtins","fromName":"Paul Tan","fromEmail":"pyokagan@gmail.com","sentAt":"2015-03-25T09:07:20Z","receivedAt":"2015-03-25T09:07:20Z","isPatch":false,"sender":{"key":"pyokagan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/109479?v=4"},"body":"Since the deadline is fast approaching, and I've read that\ngoogle-melange usually becomes overwhelmed near the deadline, I'll try\nto iterate on the proposal as much as possible. Below is v2, mostly\nsmall changes in response to Matthieu's and Junio's reviews.\n\nThe changes are as follows:\n\n* Make it clear that zero spawning of processes is an ideal -- it\n  doesn't have to be so in practice.\n\n* Swap rewrite of git-pull and git-am in timeline. It is better to push\n  the first patch to the mailing list as soon as possible.\n\n* Make it clear that as part of refactoring, commonly recurring patterns\n  can be codified and implemented in the internal git API.\n\n* Add microproject v5.\n\n* Make it clear that Windows is not the only one that has poor IO\n  performance. Poor IO performance can stem from the choice of operating\n  system, filesystem and underlying storage performance.\n\n* Cite filesystem cache feature in git for windows.\n\n* Remove section-numbering directive, github messes it up.\n\n* State what the end-product of the final stage is.\n\nThe updated version is also in the gist[1].\n\n[1] https://gist.github.com/pyokagan/1b7b0d1f4dab6ba3cef1\n\n-->8--\n\n========================================\nMake `git-pull` and `git-am` builtins\n========================================\n\n:Abstract: `git-pull` and `git-am` are frequently used git subcommands.\n           However, they are porcelain commands and implemented as shell\n           scripts, which has some limitations which can cause poor\n           performance, especially in non-POSIX environments like Windows.\n           I propose to rewrite these scripts into low level C code and make\n           them builtins.  This will increase git's portability, and may\n           improve the efficiency and performance of these commands.\n\n.. section-numbering::\n\nLimitations of shell scripts\n=============================\n\n`git-pull` is a commonly executed command to check for new changes in the\nupstream repository and, if there are, fetch and integrate them into the\ncurrent branch. `git-am` is another commonly executed command for applying a\nseries of patches from a mailbox to the current branch. They are both git\nporcelain commands -- they have no access to git's low level internal API.\nCurrently, they are implemented by the shell scripts ``git-pull.sh`` and\n``git-am.sh`` respectively. These shell scripts require a fully-functioning\nPOSIX shell and utilities. As a result, these commands are difficult to port to\nnon-POSIX environments like Windows.\n\nSince porcelain commands do not have access to git's internal API, performing\nany git-related function, no matter how trivial, requires git to be spawned in\na separate process. This limitation leads to these git commands being\nrelatively inefficient, and can cause long run times on certain platforms that\ndo not have copy-on-write ``fork()`` semantics.\n\nSpawning processes can be slow\n-------------------------------\n\nShell scripting, by itself, is severely limited in what it can do.  Performing\nmost operations in shell scripts require external executables to be called. For\nexample, ``git-pull.sh`` spawns the git executable not only to perform complex\ngit operations like `git-fetch` and `git-merge`, but it also spawns the git\nexecutable for trivial tasks such as retrieving configuration values with\n`git-config` and even quoting of command-line arguments with ``git rev-parse\n--sq-quote``. As a result, these shell scripts usually end up spawning a lot of\nprocesses.\n\nProcess spawning is usually implemented as a ``fork()`` followed by an\n``exec()`` by shells. This can be slow on systems that do not support\ncopy-on-write semantics for ``fork()``, and thus needs to duplicate the memory\nof the parent process for every ``fork()`` call -- an expensive process.\n\nFurthermore, starting up processes on Windows is generally expensive as it\nperforms `several extra steps`_ such as such as using an inter-process call to\nnotify the Windows Client/Server Runtime Subsystem(CSRSS) about the process\ncreation and checking for App Compatibility requirements.\n\n.. _`several extra steps`:\n    http://www.microsoft.com/mspress/books/sampchap/4354a.aspx\n\nThe official Windows port of git, Git for Windows, uses MSYS2 [#]_ to emulate\n``fork()``. Since Windows does not support forking semantics natively, MSYS2\ncan only emulate ``fork()`` `without copy-on-write semantics`_. Coupled with\nWindows heavy process creation, this causes huge slowdowns of git on Windows.\n\n.. _`without copy-on-write semantics`:\n    https://www.cygwin.com/faq.html#faq.api.fork\n\nA \"no-updates\" `git-pull`, for example, takes an average of 5.1s [#]_, as\ncompared to Linux which only takes an average of 0.08s. 5 seconds,\nwhile seemingly short, would seem like an eternity to a user who just wants to\nquickly fetch and merge changes from upstream.\n\n`git-am`'s implementation reads each patch from the mailbox in a while loop,\nspawning many processes for each patch. Considering the cost of spawning each\nprocess, as well as the fact that runtime grows linearly with the number of\npatches, git-am takes a long time to process a seemingly small number of\npatches on Windows as compared to Linux. A quick benchmarks shows that `git-am`\ntakes 7m 20.39s to apply 100 patches on Windows, compared to Linux, which took\nonly 0.08s.\n\nCommands which call `git-am` are also affected as well. ``git-rebase--am.sh``,\nwhich implements the default, patch-based, non-interactive rebase of the\n`git-rebase` command, is implemented by first calling `git-format-patch` (a C\nbuiltin) to generate the patches of commits to be rebased, and then applying\nthe commits on top of the new head using git-am. On Windows, the execution time\nof `git-am` currently takes up around 98% of `git-rebase`'s execution time for\nnon-interactive rebases [#]_. If `git-am` was made to perform faster,\n`git-rebase` would benefit greatly.\n\n.. [#] The current Git for Windows is based on MSYS, but shares many of the\n    limitations of MSYS2 as they are both derived from cygwin. This proposal is\n    written with MSYS2 in mind, as Git For Windows will use it in the future.\n\n.. [#] The `git-pull` from a local remote with no updates. As a benchmark,\n    `git-pull` was run with this setup 100 times on Windows and Linux boxes\n    with similar specs. `git-pull` was executed from a native process on\n    Windows to avoid MSYS2's forking overhead.\n\n.. [#] git-rebase was used to rebase 100 commits in non-interactive mode\n    with ``GIT_TRACE`` on. The timings were taken from the resulting output and\n    matched up with the code in ``git-am.sh`` and ``git-rebase--am.sh``. The\n    total execution time was 8m 0s, of which `git-format-patch` took only 0.5s,\n    but `git-am` took 7m 52s.\n\nScripting languages introduce more dependencies\n-------------------------------------------------\n\nScripting languages, while allowing for faster prototyping of commands,\nintroduce dependencies into the git distribution. The problem is greater with\nshell scripts which, due to their simple nature, need to call other executables\nto perform non-trivial tasks. `git-pull` and `git-am` combined requires `test`,\n`printf`, `echo`, `sed`, `tr`, `grep`, `cat`, `mkdir`, `rm`, `mv`, `perl` etc.\nThese may seem like common POSIX utilities, but when porting git to non-POSIX\nplatforms, these commands must all be ported and installed on the system in its\nentirety. Git for Windows, for example, requires around 250MB of disk space for\nits installation as it includes the MSYS2 shell and utilities, as well as\nlanguage runtimes for Perl and Tcl/Tk.\n\nFurthermore, should any workarounds be required to support the platform, it\nmust be implemented in all of these dependency libraries and executables. Git,\nfor example, implements a compatibility function for ``unlink()`` on Windows\nthat deals with failures that can occur if another process has an open handle\non the file [#]_. However, this only helps git builtins, and will have to be\nimplemented again on all the other dependency shell utilities. Thus, shell\nscripts do not benefit from this compatibility function, and will have to\nworkaround file deletion failures separately, leading to lots of duplicated\ncode.\n\n.. [#] See ``mingw_unlink()`` in ``compat/mingw.c``.\n\nScripts have inefficiencies\n----------------------------\n\nAs stated above, porcelain do not have access to the git internal API, and\nthus have to spawn git processes in order to perform any git-related operation,\nno matter how trivial it is. In every git invocation, git would have to re-read\nthe user's configuration files, repository index, repopulate the filesystem\ncache [#]_ etc. This leads to a lot of unnecessary IO, which on systems \nwith poor IO performance [#]_ will lead to runtime overhead as well.\n\nGit has internal caches for configuration values, the repository index and\nrepository objects. By rewriting the porcelain into C builtins and using the\ngit internal API instead of spawning separate git processes, these caches can\nbe taken advantage of to reduce redundant IO accesses.\n\n.. [#] fscache, currently only implemented in Git for Windows. See commit\n    `99943de`_.\n\n.. _`99943de`: https://github.com/git-for-windows/git/commit/99943de\n\n.. [#] Poor IO performance can stem from the choice of operating system,\n    filesystem as well as the underlying storage medium. Windows, for example,\n    is known to have worse IO performance than Linux, which git was\n    historically primarily written for. Network file systems such as NFS can\n    also cause poor IO performance due to network latency. IO performance of\n    HDDs will be lower than SSDs due to slower random access and higher\n    latency.\n\nRewriting shell scripts to C\n=============================\n\nIn order to eliminate the aforementioned portability and performance\nlimitations, I propose that these scripts be rewritten into C builtins. The C\nprogramming language provides a richer set of data types, and also provides\naccess to git's internal API. Thus, the above problems can be solved:\n\n* git is a native executable on Windows, and thus does not require MSYS2 POSIX\n  emulation. Spawning processes will not incur the overhead of MSYS2 fork\n  emulation.\n\n* Converting shell scripts into builtins will reduce the git distribution's\n  dependence on other software. In the future, if all core git functionality is\n  converted into C, it would greatly ease porting of git to platforms which\n  only require the core subset of git's functionality.\n\n* Taking advantage of git's internal API and C data types can remove the\n  inefficiencies inherent in shell scripts. For example, instead of spawning a\n  `git-config` process to get a configuration value, ``git_config_get_value()``\n  can be used. This function also takes advantage of git's configuration cache,\n  which means that configuration files only need to be read once to access all\n  of the configuration values, thus reducing IO.\n\nIn addition, `git-pull` and `git-am`'s behavior can also become more consistent\nwith other git builtin through the git internal API. Currently, command line\narguments in `git-pull` and `git-am` are parsed manually with a while loop and\npattern matching. As a result, their command line interface is inconsistent\nwith other git builtins, which use the ``parse-options`` API. For example, in\n`git-pull` the option ``--st`` should thrown an ambiguous option error as it\ncould mean ``--stat`` or ``--strategy``, but ``git-pull.sh`` is hardcoded to\nassume ``--st`` resolves to ``--strategy``. `git-pull` and `git-am` also do not\nprovide usage information with the ``-h`` flag. Rewriting these commands to use\n``parse-options`` would make their command line interfaces consistent with\nother git builtins.\n\nIn order to fully take advantage of the above benefits of implementing\n`git-pull` and `git-am` in C, especially with regards to making the resulting C\ncode as efficient and fast as possible, I propose the following requirements\nfor the rewritten code:\n\n1. Ideally [#]_, no spawning of external git processes. This is to support systems\n   with high ``fork()`` or process creation overhead, and to reduce redundant\n   IO by taking advantage of the internal object, index and configuration\n   cache.\n\n2. Avoid needless parsing/string conversions by directly accessing the C data\n   structures. Massaging of strings cause too much code churn, so functions\n   that take the richer C data types as input should be preferred over\n   functions that work by parsing string arguments.\n\nOverall, rewriting git-pull and git-am into efficient C code will most likely\nlead to impressive speedups on platforms most affected by the aforementioned\nlimitations. The `prototype rewrite of git-pull`_, for example, takes only an\naverage of 0.63s on the same \"no-updates\" benchmark. Compared to the shell\nscript which took an average of 5.1s, this is nearly an 8x improvement in\nexecution time.\n\n.. _`prototype rewrite of git-pull`:\n    http://thread.gmane.org/gmane.comp.version-control.git/265628\n\nOn the other hand, the rewritten code should not cause regressions in the\ncommand as compared to the original scripts as the time wasted on dealing with\nthe bugs may outweigh any advantages of rewriting these scripts, especially on\nplatforms which do not suffer so much from the limitations of scripts.\nTherefore, I propose the following additional requirements:\n\n3. The resulting builtin should not have wildly different behavior or bugs\n   compared to the shell script.\n\n4. The rewritten code should not be much harder to maintain than the original\n   script.\n\nThese requirements leads to some potential difficulties in rewriting `git-pull`\nand `git-am`.\n\n.. [#] This requirement needs to be balanced with the fact that significant\n    refactoring of the git codebase may be required to access certain\n    functionality without spawning a separate process. (e.g. ensuring errors\n    are propogated instead of ``die()``-ing).\n\nPotential difficulties\n=======================\n\nRewriting code may introduce bugs\n----------------------------------\n\nA dangerous possibility of rewriting code is that bugs may be introduced into\nthe rewritten version without detection. The test suite can help in catching\nsome bugs, however there is still the possibility that the test suite may not\nbe comprehensive enough. Generally, the ideal method of catching errors and\nbugs is through careful rewriting and review of the code. However, such reviews\nwould require a lot of time and effort. In order to ensure that the rewrite can\nbe completed during the GSoC period, it would be useful if the test suite could\nprovide some sort of guarantee that the rewritten code *most probably* did not\nintroduce any bugs. For this purpose, code coverage tools can be used to ensure\nthat the test suite for the command tests all major code paths in the rewritten\nbuilt-in.\n\nWe can also avoid introducing logical errors by following the logical structure\nof the original script in the rewritten code.  This means largely doing a\nline-by-line, one-to-one translation of the shell script into C. For instance,\nthis line in ``git-pull.sh`` calls `git-merge-base` to calculate the point in\nhistory in which ``$curr_branch``, the current branch, forked from the upstream\nremote tracking branch, ``$remoteref``::\n\n    oldremoteref=$(git merge-base --fork-point \"$remoteref\" $curr_branch 2>/dev/null)\n\nAssuming ``remoteref`` and ``curr_branch`` are strings, the equivalent C code,\nusing the ``run-command`` API, would look like::\n\n    struct child_process cmd = CHILD_PROCESS_INIT;\n    struct strbuf oldremoteref = STRBUF_INIT;\n    argv_array_pushl(&cmd.args, \"merge-base\", \"--fork-point\", remoteref, curr_branch, NULL);\n    cmd.out = -1;\n    cmd.no_stderr = 1;\n    cmd.git_cmd = 1;\n    if (!start_command(&cmd)) {\n        strbuf_read(&oldremoteref, cmd.out, 0);\n        close(cmd.out);\n        finish_command(&cmd);\n    }\n\nOf course, the downside of following this too strictly is that if there were\nany logical bugs in the original code, or if the original code is unclear, the\nrewritten code would inherit these problems too. For example, the code in\n``git-pull.sh`` assumes in certain code paths that the repository and refspecs\nto fetch are the only arguments present in ``\"$@\"``. However, the ``\"$@\"``\nautomatic variable would also contain the command-line options to be passed to\n`git-fetch` as well [#]_. The rewritten `git-pull` should, for the purpose of\nmaking code maintenance easy, fix these logical errors.\n\n.. [#] An example of such an assumption can be found in\n    ``remoteref=\"$(get_remote_merge_branch \"$@\" 2>/dev/null)\"``.\n    ``get_remote_merge_branch`` assumes that the first argument is the remote\n    name, and will thus fail (silently) if it ends up being arguments for\n    git-fetch.\n\nRewritten code may become harder to understand\n-----------------------------------------------\n\nFor the purpose of reducing git's dependencies, the rewritten C code should not\ndepend on other libraries or executables other than what is already available\nto git builtins. However, C is a much more verbose language than shell script,\nand does not provide much advanced facilities for processing text.  As a\nresult, text processing functions in shell scripts can end up as huge\nmulti-line functions in C. For instance, in ``git-pull.sh``, by relying on\n`sed` and `tr`, all heads valid for merge from ``FETCH_HEAD`` can be retrieved\nwith a single short-and-succinct pipeline::\n\n    merge_head=$(sed -e '/\tnot-for-merge\t/d' \\\n        -e 's/\t.*//' \"$GIT_DIR\"/FETCH_HEAD | \\\n        tr '\\012' ' ')\n\nA strict translation of the pipeline to C becomes something like::\n\n    struct strbuf merge_head = STRBUF_INIT;\n    FILE *fp = fopen(git_path(\"FETCH_HEAD\"), \"r\");\n    for (;;) {\n        char sha1_text[40];\n        char text[128];\n        int c, ret;\n\n        ret = fscanf(fp, \"%40c %127[^\\n]\", sha1_text, text);\n        if (ret == EOF)\n            break;\n        else if (ret != 2)\n            die(_(\"error parsing %s\"), filename);\n        for (;;) {\n            c = fgetc(fp);\n            if (c == '\\n' || c == EOF)\n                break;\n        }\n        if (strstr(text, \"not-for-merge\"))\n            continue;\n        strbuf_addstr(merge_head, sha1_text);\n        strbuf_addstr(merge_head, \" \");\n    }\n    fclose(fp);\n\nWe can see that the C version requires much more lines compared to the shell\npipeline, which will contributes to the \"bloating\" of the C code. It may even\nseem to be more cryptic. This is a known trade-off of the C programming\nlanguage, and not depending on external libraries and dependencies. The best\nsolution is to improve the design of the rewritten code. For example, the above\ncan be moved into an appropriately-named function. The function can then be\ndocumented with well-defined inputs, outputs, and behavior. This should help\nthe resultant code to be much more understandable.\n\nRecurring code patterns, once identified, can be codified and implemented in\nthe internal git API itself. This not only helps to shrink the C code, but it\ncan also benefit the rest of the git code base.\n\nDevelopment approach and deliverables\n======================================\n\nIn the first stage (and throughout the course of the project), test suite code\ncoverage for each command is reviewed using `kcov`_ [#]_. At the minimum, the\ntest suite should cover the major code paths and command-line switches of the\nscript. These tests do not necessarily have to be perfect or comprehensive\nbefore the next stage can begin [#]_, however the minimum required tests must\nbe identified and written in order to give a good idea of what needs to be\ntested, and provides a safety net for the later stages. Tests will be kept in a\nseparate patch queue as they are applicable whether `git-pull` and `git-am` are\nbuiltins or not. By the end of the project, the test suite for `git-pull` and\n`git-am` will be more comprehensive.\n\n.. _kcov: http://simonkagstrom.github.io/kcov/\n\nIn the second stage, the shell scripts are translated line-by-line into their\ncorresponding C code. The translation should not be overly strict -- where\nappropriate the corresponding git internal API functionality can be used\ninstead. For example, in `git-pull` and `git-am` the ``parse-options`` API can\nbe used instead of manually implementing command-line argument parsing like how\nthe shell scripts currently do. If the shell script has any obvious bugs or\nerrors (perhaps identified in the first stage), they should be fixed in this\nstage as well. The resultant C code at the end of this stage may not\nnecessarily be efficient, but it should be functionally complete and error\nfree to serve as a baseline product for the final stage. The final product\nwould most probably look something like the `prototype rewrite of git-pull`_,\nbut with more usage of the run-command APIs and without the bugs.\n\n.. _`prototype rewrite of git-pull`:\n    http://thread.gmane.org/gmane.comp.version-control.git/265628\n\nIn the final stage, the baseline C code will be optimized for speed and\nefficiency. For prioritization of efforts, the baseline builtins will be\nprofiled using their respective test suites in order to find hotspots.\nThe builtins will also be benchmarked to compare their performance\nwith the original shell scripts. Since `git-pull` is just a simple wrapper\naround `git-fetch`, `git-merge` and `git-rebase`, the benchmark will simply\nconcentrate on run time for common use cases. (e.g. the \"no updates\" use case).\nFor `git-am`, the benchmark can rely on its performance when applying a large\nnumber of patches (e.g. a `patchbomb benchmark`_).\n\n.. _`patchbomb benchmark`:\n    http://thread.gmane.org/gmane.comp.version-control.git/1681/focus=2369\n\nShould there be no hotspots found, general optimization will be done to reduce\noverhead. ``run-command`` API calls will be replaced with the relevant\ncorresponding git internal API calls. Strings will be replaced with their\ncorresponding git C data types where possible to avoid needless string\nconversions. For example, SHA1s will be parsed once and stored in ``unsigned\nchar[20]`` or ``sha1_array`` data types. Some refactoring may also be required.\nFor example, for `git-pull` to access ``git-merge-base --fork-point``\nfunctionality without spawning a separate process, the function\n``handle_fork_point()`` in ``builtin/merge-base.c`` must be made available. The\nfunction must also be modified to not call ``die()`` on errors. In order to\nhelp speed up polishing and code review, this optimization will be done\niteratively in small patches on top of the baseline C code produced in stage 2.\nThe final product of this stage, and the entire project, would be a patch\nseries containing the baseline C code as the first patch, and optimizations to\nit in subsequent patches.\n\n.. [#] An example kcov code coverage report for the git-pull tests can be found\n    `here`_\n\n.. _here: https://83dc3588620c5a97164396ec753a2fa480f6a7b0-www.googledrive.com/host/0B4O2AiYulllpfmJlTW4xT050OVVicnNWWS02dm52aTJ2TFIwQ2QwdWh0VHotSkU4eUNNWjg/git-pull/git-pull.360f32c2.html\n\n.. [#] In fact, improvements to the test suite will most likely proceed in\n    parallel with the rest of the project as the process of studying and\n    rewriting the shell scripts will provide insights on what needs to be\n    tested.\n\nTimeline\n=========\n\nUnfortunately, my university term begins on the 3rd of August. On the other\nhand, though, I am currently not attending university so I'm effectively free\nbefore the Summer holidays even begin. As such, to compensate, I will begin\ncoding right after accepted student proposals are announced so that the period\nfor coding is still 3 months.\n\nThe timeline is as follows:\n\n* Apr 27: Accepted student proposals announced.\n\n* Apr 27: Stage 1 begins: Review of test suite coverage.\n\n* Apr 27 onwards: Discussion of any bugs or behavior in `git-am` and\n  `git-pull` that should be fixed or changed. This will continue throughout the\n  project.\n\n* May 4: Stage 2 (Baseline rewrite) begins.\n\n* May 4 - May 10 (1 week): Full baseline rewrite of ``git-pull.sh``.\n\n* May 11: 1st version of ``builtin/pull.c`` published on mailing list for\n  review.\n\n* May 11 - May 24 (2 weeks): Full baseline rewrite of ``git-am.sh``.\n\n* May 25: 1st version of ``builtin/am.c`` published on mailing list for review.\n\n* May 25 - Jun 22 (5 weeks): ``builtin/am.c`` and ``builtin/pull.c`` are\n  iterated on in an alternating fashion to pass code review.\n\n* Jun 22: Stage 3 (Optimization) begins\n\n* Jun 22 - Jun 24: Benchmarking and profiling is done on the new builtins,\n  especially as compared to their original shell scripts, to check for any\n  performance improvements and to guide optimization. These results are\n  published to mailing list and discussed.\n\n* Jun 24 - Jul 19 (3.5 weeks): Stage 3 (Optimization). ``builtin/am.c`` and\n  ``builtin/pull.c`` are iterated on in an alternating fashion to optimize the\n  code in small steps.\n\n* Jul 3: Mid-term evaluations deadline\n\n* Jul 20 - Aug 2 (2 weeks): Pencils down -- focus on polishing up\n  ``builtin/am.c``, ``builtin/pull.c`` and the tests patch series, and get them\n  to pass code review.\n\n* Aug 17: Suggested 'pencils-down' date.\n\n* Aug 21: Firm 'pencils-down' date.\n\n* Aug 28: Final evaluation deadline\n\nAbout me\n=========\n\nI've been accepted to the `National University of Singapore`_ for a bachelors\nin Computer Engineering, and will matriculate on 3rd August 2015. I've been\nwriting Python, C and C++ for around 4 years, and some of my experiments can be\nfound on my `github profile`_. I have also contributed patches successfully to\n`libuv`_ and `node-contextify`_.\n\nMy microproject is to implement ``XDG_CONFIG_HOME support`` in\ngit-credential-store. Patch series: `v5`_, `v4`_, `v3`_, `v2`_, `v1`_.\n\n.. _`National University of Singapore`: http://www.ceg.nus.edu.sg/\n\n.. _`github profile`: https://github.com/pyokagan\n\n.. _`libuv`: https://github.com/joyent/libuv/commit/347000929de775ae6b975a2959f5fabe81d6f1f0\n\n.. _`node-contextify`: https://github.com/brianmcd/contextify/commit/7e3e0a89779cd892b3d8604795b6675d6aecff17\n\n.. _v1: http://thread.gmane.org/gmane.comp.version-control.git/264682\n\n.. _v2: http://thread.gmane.org/gmane.comp.version-control.git/265042\n\n.. _v3: http://thread.gmane.org/gmane.comp.version-control.git/265305\n\n.. _v4: http://thread.gmane.org/gmane.comp.version-control.git/265683\n\n.. _v5: http://thread.gmane.org/gmane.comp.version-control.git/266175\n"},{"id":"258509","messageId":"xmqq4mp92c9h.fsf@gitster.dls.corp.google.com","threadId":"38905","inReplyTo":"CACRoPnTL78ZrqPYYNPkNcW7vConHZXZ66z5P2=3HySrtmZKcrg@mail.gmail.com","subject":"Re: [RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-25T17:54:50Z","receivedAt":"2015-03-25T17:54:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Paul Tan <pyokagan@gmail.com> writes:\n\n> I think it's still good to have the ideal in mind though (and whoops I\n> forgot to put in the word \"ideal\" in the text).\n\nUsing or not using fork is merely one of the trade-offs we can make.\n\n\"If all other things are equal, no fork is better than a fork\" is a\nmeaningless statement, as all other things are never equal in real\nlife---doing things internally will have a cost of having to clean\nup and a risk to get that part wrong, for example.  Engineering is a\nfine balancing act and setting an absolute goal is not a healthy\nattitude.\n"},{"id":"258523","messageId":"55131B5C.90109@gmail.com","threadId":"38905","inReplyTo":"20150324163730.GA8366@yoshi.chippynet.com","subject":"Re: [RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Sebastian Schuberth","fromEmail":"sschuberth@gmail.com","sentAt":"2015-03-25T20:32:28Z","receivedAt":"2015-03-25T20:32:28Z","isPatch":false,"sender":{"key":"sschuberth@gmail.com","avatar":"https://avatars.githubusercontent.com/u/349154?v=4"},"body":"On 24.03.2015 17:37, Paul Tan wrote:\n\n> I'm applying for git in the Google Summer of Code this year. For my\n> project, I propose to rewrite git-pull.sh and git-am.sh into fast\n> optimized C builtins. I've already hacked up a prototype of a builtin\n> git-pull in [1], and it showed a promising 8x improvement in execution\n> time on Windows.\n\nI cannot thank you enough for starting this effort. As one of the \nproject owners of Git for Windows I can confirm the (shell) script Git \ncommands to be a major source of pain.\n\nI really hope your proposal gets accepted and you'll be able to \nsuccessfully complete this task.\n\nAll the best!\n\n-- \nSebastian Schuberth\n"},{"id":"258533","messageId":"CACRoPnQusL85-ZOoM3Mg579eyvcL=BOgzz6KsnnNC5hRY9uAFw@mail.gmail.com","threadId":"38905","inReplyTo":"xmqq4mp92c9h.fsf@gitster.dls.corp.google.com","subject":"Re: [RFC/GSoC] Proposal: Make git-pull and git-am builtins","fromName":"Paul Tan","fromEmail":"pyokagan@gmail.com","sentAt":"2015-03-26T05:02:54Z","receivedAt":"2015-03-26T05:02:54Z","isPatch":false,"sender":{"key":"pyokagan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/109479?v=4"},"body":"On Thu, Mar 26, 2015 at 1:54 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Paul Tan <pyokagan@gmail.com> writes:\n>\n>> I think it's still good to have the ideal in mind though (and whoops I\n>> forgot to put in the word \"ideal\" in the text).\n>\n> Using or not using fork is merely one of the trade-offs we can make.\n>\n> \"If all other things are equal, no fork is better than a fork\" is a\n> meaningless statement, as all other things are never equal in real\n> life---doing things internally will have a cost of having to clean\n> up and a risk to get that part wrong, for example.  Engineering is a\n> fine balancing act and setting an absolute goal is not a healthy\n> attitude.\n\nNo, I do not mean \"all other things are equal\", I meant \"all other\nthings are ideal\", meaning that human factors are not involved.\n\nI thought we were in agreement that calling functions in the internal\nAPI is technically superior to forking, assuming that there are no\nbugs or errors. Isn't this one of the reasons why libgit2 exists? If\nfor whatever reason spawning an external git process is chosen, it\nwould be because rewriting all the code paths without committing any\nerrors would take too much effort.\n\nI will switch the word \"requirements\" to the word \"guidelines\" to make\nit sound less strict. However my above point still stands.\n"}]}