)]}'
{
  "commit": "835cc0c8477fdbc59e0217891d6f11061b1ac4e2",
  "tree": "be179915300e6d6ea61c8458c7e1ccb764065ed4",
  "parents": [
    "d6a2eedfddcded92c8f9b0ac022a99c4134696b0"
  ],
  "author": {
    "name": "Don Mullis",
    "email": "don.mullis@gmail.com",
    "time": "Fri Mar 05 13:43:15 2010 -0800"
  },
  "committer": {
    "name": "Linus Torvalds",
    "email": "torvalds@linux-foundation.org",
    "time": "Sat Mar 06 11:26:35 2010 -0800"
  },
  "message": "lib: more scalable list_sort()\n\nXFS and UBIFS can pass long lists to list_sort(); this alternative\nimplementation scales better, reaching ~3x performance gain when list\nlength exceeds the L2 cache size.\n\nStand-alone program timings were run on a Core 2 duo L1\u003d32KB L2\u003d4MB,\ngcc-4.4, with flags extracted from an Ubuntu kernel build.  Object size is\n581 bytes compared to 455 for Mark J.  Roberts\u0027 code.\n\nWorst case for either implementation is a list length just over a power of\ntwo, and to roughly the same degree, so here are timing results for a\nrange of 2^N+1 lengths.  List elements were 16 bytes each including malloc\noverhead; initial order was random.\n\n                      time (msec)\n                      Tatham-Roberts\n                      |       generic-Mullis-v2\nloop_count  length    |       |    ratio\n4000000       2     206     294    1.427\n2000000       3     176     227    1.289\n1000000       5     199     172    0.864\n 500000       9     235     178    0.757\n 250000      17     243     182    0.748\n 125000      33     261     196    0.750\n  62500      65     277     209    0.754\n  31250     129     292     219    0.75\n  15625     257     317     235    0.741\n   7812     513     340     252    0.741\n   3906    1025     362     267    0.737\n   1953    2049     388     283    0.729  ~ L1 size\n    976    4097     556     323    0.580\n    488    8193     678     361    0.532\n    244   16385     773     395    0.510\n    122   32769     844     418    0.495\n     61   65537     917     454    0.495\n     30  131073    1128     543    0.481\n     15  262145    2355     869    0.369  ~ L2 size\n      7  524289    5597    1714    0.306\n      3 1048577    6218    2022    0.325\n\nMark\u0027s code does not actually implement the usual or generic mergesort,\nbut rather a variant from Simon Tatham described here:\n\n    http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html\n\nSimon\u0027s algorithm performs O(log N) passes over the entire input list,\ndoing merges of sublists that double in size on each pass.  The generic\nalgorithm instead merges pairs of equal length lists as early as possible,\nin recursive order.  For either algorithm, the elements that extend the\nlist beyond power-of-two length are a special case, handled as nearly as\npossible as a \"rounding-up\" to a full POT.\n\nSome intuition for the locality of reference implications of merge order\nmay be gotten by watching this animation:\n\n    http://www.sorting-algorithms.com/merge-sort\n\nSimon\u0027s algorithm requires only O(1) extra space rather than the generic\nalgorithm\u0027s O(log N), but in my non-recursive implementation the actual\nO(log N) data is merely a vector of ~20 pointers, which I\u0027ve put on the\nstack.\n\nLong-running list_sort() calls: If the list passed in may be long, or the\nclient\u0027s cmp() callback function is slow, the client\u0027s cmp() may\nperiodically invoke cond_resched() to voluntarily yield the CPU.  All\ninner loops of list_sort() call back to cmp().\n\nStability of the sort: distinct elements that compare equal emerge from\nthe sort in the same order as with Mark\u0027s code, for simple test cases.  A\nboot-time test is provided to verify this and other correctness\nrequirements.\n\nA kernel that uses drm.ko appears to run normally with this change; I have\nno suitable hardware to similarly test the use by UBIFS.\n\n[akpm@linux-foundation.org: style tweaks, fix comment, make list_sort_test __init]\nSigned-off-by: Don Mullis \u003cdon.mullis@gmail.com\u003e\nCc: Dave Airlie \u003cairlied@redhat.com\u003e\nCc: Andi Kleen \u003candi@firstfloor.org\u003e\nCc: Dave Chinner \u003cdavid@fromorbit.com\u003e\nCc: Artem Bityutskiy \u003cdedekind@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "19d11e0bb958a874fe7f560f25c75e392cd47aea",
      "old_mode": 33188,
      "old_path": "lib/list_sort.c",
      "new_id": "362c10f1653f842083accdceed155e370de38dcb",
      "new_mode": 33188,
      "new_path": "lib/list_sort.c"
    }
  ]
}