{"thread":{"id":"46842","subject":"Re: Speeding up history traversals with caches","startedAt":"2017-09-27T08:09:54Z","lastAt":"2017-09-27T08:09:54Z","messageCount":1,"participants":["Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"329031","messageId":"20170927080928.g76qjnohm3645w3o@sigill.intra.peff.net","threadId":"46842","inReplyTo":"CAGdZCnE-5CUxc-1PSSYagfXE9HMhu9k8xpo8rwM1K_urmY8gHw@mail.gmail.com","subject":"Re: Speeding up history traversals with caches","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-27T08:09:29Z","receivedAt":"2017-09-27T08:09:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 25, 2017 at 05:28:43PM -0700, Sabelo Mhlambi wrote:\n\n> Hi Jeff (and the Git community),\n> \n> As my intro to open source contributions I'd like to attempt the \"Speeding\n> up history traversals with caches\" as outlined here\n> https://git.github.io/Outreachy-15/.\n> \n> It seems like a challenging and worthwhile problem. May I have more\n> information on the project and on how to get get started on the application.\n> \n> Thanks!\n\nHi Sabelo, welcome to Git!\n\nUnfortunately your message didn't make it to the mailing list, because\nthe list software is strict about messages not including any HTML parts.\nIt looks like you're using Gmail; you'll need to ask it to send\nplain-text emails.\n\nThe general idea of the project is: a lot of git commands need to access\ncommit objects to walk the history graph, but they're expensive to\naccess because we have to inflate the whole commit object from disk.\nWhat I'd like to have instead is a compact representation that we can\nquickly use to get the main interesting data out of a commit message\nwithout having to inflate all of the bytes.\n\nI did a prototype of this a few years ago:\n\n  https://public-inbox.org/git/20130129091434.GA6975@sigill.intra.peff.net/\n\nCompared to those patches, there are a lot of possible things to work\non:\n\n  - the code needs cleaned up and ported to a more modern git\n\n  - the implementation is a bit complex; it was anticipating having\n    several types of auxiliary files, but probably we really just need\n    one\n\n  - we've also discussed storing computed data about the graph, such as\n    generation numbers, which can help speed up some traversals\n\n  - we may be able to cache some interesting tree data (e.g., bitmaps of\n    which paths are touched by a particular commit).\n\nI wouldn't expect us to cover all of that during the internship period,\nbut it gives a sense of the possible directions.\n\nThat thread may work as a starting point for understanding the problem\nspace. You can also probably find some interesting discussions if you\nsearch for \"generation number\" in the mailing list archive at\nhttps://public-inbox.org/git.\n\nThe first step is probably to get comfortable with building Git and\nsubmitting a small patch. Christian posted some advice on finding a\ntopic to work on:\n\n  https://public-inbox.org/git/CAP8UFD3vPQHJZNt1+egKkshiyqrGKiJp7eWU-Es6bTLgvXe1Kg@mail.gmail.com/\n\nLet us know if you get stuck or if you have any questions!\n\n-Peff\n"}]}