{"thread":{"id":"12682","subject":"[announce] (nearly) full jgit revision machinary","startedAt":"2008-03-14T07:20:00Z","lastAt":"2008-03-14T07:20:00Z","messageCount":1,"participants":["Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"72042","messageId":"20080314072000.GX8410@spearce.org","threadId":"12682","inReplyTo":null,"subject":"[announce] (nearly) full jgit revision machinary","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-03-14T07:20:00Z","receivedAt":"2008-03-14T07:20:00Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"I have a nearly complete revision machinary implementation for jgit.\nThe series follows on top of my pack index v2 work, which is in my\nmaster branch of repo.or.cz/egit/spearce.git.\n\nThis series started because I found the History view was just too\nslow for words.  Running JProbe on Eclipse pointed out that our\nexisting revision walking code was not up to the challenge of a\nreal-world sized repository.\n\nHere goes a summary...  series is here:\n\n    git://repo.or.cz/egit/spearce.git revwalk\n\n\n  Fixes and cleanups\n  ------------------\n    * Correct unsigned integer conversion issues\n    * Include refs/remotes as part of the ref search path\n    * Only use bytes 1-5 for a SHA-1 ObjectId hashCode\n    * Fix the OBJECT_ID_LENGTH constant at 20\n    * Hand unroll the ObjectId.equals method\n    * Don't bother caching commits in the delta base cache\n    * Teach FileMode how to return the proper instance of itself\n    * Teach FileMode about S_IFGITLINK being 0160000\n    * Teach FileMode about MISSING being 0\n\n    These have nothing to do with the series directly, but were\n    done to improve its code or fix some earlier bugs.\n\n\n  Revision Machinary\n  ------------------\n    * New revision walking library for jgit\n    * Teach RevWalk about uninteresting commits\n    * Document the flag constants used in RevWalk\n    * Implement a commit filtering API for RevWalk\n    * Make all RevFilter implementations cloneable\n    * Allow RevFilters to break out of the main walk loop\n    * Implement a commit time based RevFilter for before/after filtering\n    * Refactor basic commit walking from RevWalk to a streamable iterator API\n    * Evaluate RevFilters before inserting parent commits to pending\n    * Dispose of a RevCommit as soon as it is no longer interesting\n    * Use a FIFO queue of RevCommit during reset rather than sorting by date\n\n    Aside from --topo-order this is a nearly full revision machinary.\n    Features like --author, --committer, --grep, --not, all work.\n    We don't parse \"A..B\" but we can do it as \"A --not B\", or\n    \"A ^B ^C D\".\n\n    The package's performance on Java 6/x86/Windows is well within\n    spitting distance of Git on Cygwin.  I'm seeing jgit take just\n    over 50 ms longer to produce back ~13,000 commits.\n\n    I'll get --topo-order done soon, most likely this weekend. It\n    will probably also get an incremental restart trick like we do\n    in C Git, where we shovel the data out as early as we can but\n    signal a restart if topo order was violated.\n\n    Memory can still be reduced a tad, but its fast as heck.\n    Our main suckage for memory is the ObjectId class.  On a modern\n    HotSpot JVM it costs 44 bytes to store a 20 byte SHA-1.  I think\n    our second main suckage is the ObjectIdMap.  java.util.HashMap is\n    not that efficient when it comes to memory usage.\n\n\n  Tree Diff\n  ---------\n    * New tree walking library for jgit\n    * Implement a tree entry filtering API for TreeWalk\n    * Define a path limiter for TreeWalk to reduce results\n\n    Turns out the Tree class is too slow for serious work.  This is\n    a concurrent tree walker that can do an N-way difference of\n    an arbitrary number of trees, recursively and shallow.  We can\n    also limit the difference to only entries matching a particular\n    filter expression.\n\n    I spent a good amount of time tuning this library, but it\n    probably can still benefit from more micro-optimization.  Java is\n    just dog slow, but I think we're doing almost the best we can.\n\n    At present this library only does tree objects, but it should\n    also be able to walk the local filesystem and an index (or\n    two or three) concurrently with trees.  I'll implement those\n    other iterators in the near future.\n\n\n  Path Limiter & Parent Rewrites\n  ------------------------------\n    * Implement path limited revision walking and parent rewriting\n    * Allow revwalk and treewalk to directly access cached object data\n\n    These changes give us functionality like \"git log HEAD -- foo.c\",\n    where the DAG gets subsetted down to only those commits that\n    had an interesting change against foo.c.  Yes, it also works\n    on directories and combinations of paths.\n\n    I've done a bunch of manual testing and differencing against\n    the C Git output for the same inputs, and jgit is producing\n    identical results.  That's with \"--parents\".  So we can now\n    get a dense, plottable subsetted DAG. Yay.\n\n    When the path limiter is enabled we spend ~98% of our CPU time\n    inside of the treewalk package introduced above for the tree\n    difference feature.  Its horribly slow.  If the path we are\n    looking for is early enough in the tree we're not too far off\n    from C Git's performance, but try matching on say \"t\" and the\n    world falls over.  We are 4x slower.\n\n\n  Fixes and cleanups\n  ------------------\n    * Implement some basic command line programs built on top of jgit\n\n    This a \"jgit\" command line wrapper, along with basic subcommand\n    tools like \"log\", \"rev-list\", \"ls-tree\" and \"diff-tree\", all\n    built on top of the above functionality.  jgit is starting to\n    feel like it is actually capable of doing some of the major\n    functions C Git does.\n\n    \"jgit log | less\" has a slight lag before the first commit when\n    compared to \"git log\", but is still faster than \"svn log\".  ;-\n\n\n-- \nShawn.\n"}]}