{"thread":{"id":"43176","subject":"On performance characteristics of pickaxe with -M, -C, and -C -C","startedAt":"2006-11-05T22:27:10Z","lastAt":"2006-11-05T22:27:10Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"293976","messageId":"7v4ptdo7gh.fsf@assigned-by-dhcp.cox.net","threadId":"43176","inReplyTo":null,"subject":"On performance characteristics of pickaxe with -M, -C, and -C -C","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-11-05T22:27:10Z","receivedAt":"2006-11-05T22:27:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've been brewing parts of git-pickaxe in \"pu\" for the last week\nto fix both correctness and performance issues, and it appears\nit is now in a good enough shape to even replace git-blame for\neveryday use, so I've placed my recent work in \"next\".\n\n - Under -M or -C, it tried to find lines that are copied\n around, but it did its scan only once. When a scan result\n splits the blame for a block of lines into three blocks:\n\n original span of blame <----------------------------->\n lines matched by -M/-C <-----> \n\n ==>\n\n result of split <---------><.....><----------->\n\n the middle part that matched passed the blame to the parent,\n but the new two parts created by this split was not\n re-scanned by the old code and the blame stayed with the\n commit we were inspecting. The updated code re-scans for\n these two new parts and allows them to pass blame to their\n parents.\n\n - The implementation of -C -C (aka \"find copies harder\") was\n very broken. Under this flag, the program should try all the\n paths in the parent as the candidates of copies for a path\n that is new (that is, not a modification from the original\n path, nor rename/copy from an existing path). However, it\n used diffcore incorrectly and used only the paths that were\n changed from parent to child (i.e. the same as a single -C).\n The updated code works as advertised. This is very expensive\n but the option exists in case when you know you want to pay\n the price to find out all the possible cuts-and-pastes.\n\n - The old code was reading each blob typically twice -- once as\n the \"parent's blob\" when a commit is compared with its\n parent, and then as the \"child's blob\" when that parent was\n trying to pass the blame to its parent. The updated code\n reuses these blobs between the parent and the child and is\n much more efficient.\n\nThe following is by no means a scientific test, but here are two\ncomparisons using blame and pickaxe with or without -M/-C/-C -C.\nOne is our own revision.c, and the other is kernel/sched.c from\nthe kernel project. The number of minor faults in 'time' output\ngives a rough indication of the memory footprint of the process.\n\n----------------------------------------------------------------\n\n* git-blame revision.c\n0.76user 0.01system 0:00.77elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+3269minor)pagefaults 0swaps\nreads blob 82 times\n\n* git-pickaxe revision.c\n0.78user 0.00system 0:00.78elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+2500minor)pagefaults 0swaps\nreads blob 92 times\n\n These two give comparable results. The only difference is\n that git-blame says line 319 is from a41e109c (2006-03-12)\n while git-pickaxe says it is from 8efdc326 (2006-03-10).\n Manual inspection of both tells me that they are both valid\n and reasonable.\n\n* git-pickaxe -M revision.c\n0.95user 0.02system 0:00.97elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+2410minor)pagefaults 0swaps\nreads blob 92 times\n\n This notices that ll. 528-531, 695-701 and 791-794 are not\n new lines introduced by the commits git-blame and\n git-pickaxe without -M place blame on, but the commits just\n shuffled existing lines. For an example, look at output\n from:\n\n\tgit show 53069686 -- revision.c\n\n The commit moved around the code to parse --min-age= option;\n git-pickaxe -M does not blame 53069686 for it, but git-blame\n and git-pickaxe without -M do.\n\n Because this flag does not cause the command to look for\n copied lines across files (other than the usual rename\n detection), the set of blobs it works on is the same as the\n command without -M.\n\n* git-pickaxe -C revision.c\n2.52user 0.03system 0:02.55elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+5262minor)pagefaults 0swaps\nreads blob 486 times\n\n This starts noticing that a lot of the code actually came\n from rev-list.c as mentioned in an earlier message by Linus.\n\n\tMessage-ID: \n\n To find new suspects that are not the same path (or renamed\n path) in the parent, the program inspects files that were\n changed from its parent and that is how it finds that many\n lines came from rev-list.c. Because it needs to work on\n more blobs than the above cases, it is a heavier weight\n operation.\n\n* git-pickaxe -C -C revision.c\n10.60user 0.06system 0:10.66elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+19762minor)pagefaults 0swaps\nreads blob 1839 times\n\n This does not notice anything new compared to the above for\n this file's history.\n\n----------------------------------------------------------------\n\n* git-blame kernel/sched.c\n4.68user 0.63system 0:05.31elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+276957minor)pagefaults 0swaps\nreads blob 177 times\n\n* git-pickaxe kernel/sched.c\n5.63user 0.66system 0:06.29elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+276274minor)pagefaults 0swaps\nreads blob 181 times\n\n The above two produce identical results.\n\n* git-pickaxe -M kernel/sched.c\n9.62user 1.35system 0:10.96elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+388517minor)pagefaults 0swaps\nreads blob 181 times\n\n The story is the same as in our earlier example on revision.c.\n For example, look for comments about \"task_timeslice()\" in:\n\n git show 91fcdd4e -- kernel/sched.c\n\n* git-pickaxe -C kernel/sched.c\n12.94user 1.08system 0:14.04elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+407624minor)pagefaults 0swaps\nreads blob 667 times\n\n This notices that many lines came from arch/ia64/kernel/domain.c\n\n* git-pickaxe -C -C kernel/sched.c\n13.09user 1.02system 0:14.11elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+407626minor)pagefaults 0swaps\nreads blob 667 times\n\n For the kernel history (since 2.6.12-rc2) kernel/sched.c is not\n a new file, so there is no difference in the output or\n performance between -C and -C -C.\n"}]}