7 ms·

On the Worst-Case Complexity of TimSort

204 points by pelario 8y ago

julienfr112 8y ago
Amazing there is still something to find in a sort algorithm.
- lorenzhs 8y ago
  Especially when targeting realistic machine models, there are a lot of things that are suboptimal about the classical sorting algorithms like quicksort or mergesort. For example, a quicksort with perfect choice of pivot will incur a branch miss with probability 50% for every element. That's not something classical complexity analysis measures, but on actual CPUs, branch misses have quite an impact (something like 10–15 cycles). Shameless plug for something I once built for a lecture to demonstrate this: https://github.com/lorenzhs/quicksort-pivot-imbalance https://github.com/lorenzhs/quicksort-pivot-imbalance For sorting algorithms that take the behaviour of modern CPUs into account, check out ips4o (https://arxiv.org/abs/1705.02257 https://arxiv.org/abs/1705.02257, code: https://github.com/SaschaWitt/ips4o https://github.com/SaschaWitt/ips4o) or for a simpler algorithm that's still much faster than quicksort in most cases, blockquicksort (https://arxiv.org/abs/1604.06697 https://arxiv.org/abs/1604.06697, code: https://github.com/weissan/BlockQuicksort https://github.com/weissan/BlockQuicksort). Note that both papers were published in the last two years :) Of course these algorithms are much more complex and error-prone to implement and use some additional memory, which may explain why they're not used in standard library implementations of popular languages.
  - rthomas6 8y ago
    This is awesome!
  - kjeetgill 8y ago
    Out of curiosity, what do you read/follow that makes stuff like this discoverable?
    - lorenzhs 8y ago
      I'm a PhD student in algorithmics / algorithm engineering, so I work with a lot of people who do stuff like this, even though my research isn't related to sorting. Super Scalar Sample Sort (which ips4o is based on) was co-authored by my advisor, Peter Sanders, and I re-implemented it a few years ago in modern C++ just for the fun of it. Turns out that was a lot nicer to read than the original code (which isn't public) and a bit faster, too. I put that on GitHub where the blockquicksort authors found it and contacted me and we traded some emails and made some improvements. Sometime later my advisor and two colleagues came up with an idea for in-place super-scalar sample sort, out of which eventually ips4o was born. So, uh, I guess I just work with the right people :) Sorry that I can't give you anything concrete. All of these papers were presented at ESA (European Symposium on Algorithms), though, so that's a good venue to follow. But beware, ESA has a theory track that's a lot bigger than the experimental track, and papers published there can be somewhat unapproachable ;)
      - kjeetgill 8y ago
        Ahh, that makes sense, thanks! I'd recently asked elsewhere 'I've always wondered is there a good mathematical representation of an algorithm that is useful for algebraic manipulation? Like producing a quicksort from bubble sort.' And got linked this paper [0]. This is only time I've heard the word 'Algoritmics' since that. Any interesting 'entry level' reads you could send my way? [0]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.2247&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45....
        lorenzhs 8y ago
        Thanks for the link, that was fun to read (well, skim). I don't think the term 'algorithmics' appears very often in publications, it's more of an umbrella term for many things. The stuff we work in our group is sort of the practical side of theoretical computer science, in that our focus is on algorithms that can be efficiently implemented and don't just look good on paper. The methodology is called Algorithm Engineering, it's described quite well in https://en.wikipedia.org/wiki/Algorithm_engineering https://en.wikipedia.org/wiki/Algorithm_engineering. Apart from ESA's track B, the major conferences there are Alenex and SEA (Symposium on Experimental Algorithms). All three are open access. It's difficult to recommend anything in particular, not only because the scope is very broad, but also because most papers aren't written for a wide audience. Good writing is not something that academics optimize for (perversely, good writing can be seen as a negative point, in that if a paper is easy to understand, it may be rejected for being too simple), nor is it taught. Maybe something like https://github.com/papers-we-love/papers-we-love https://github.com/papers-we-love/papers-we-love could serve as a starting point?
  - notriddle 8y ago
    You probably want to use pdqsort, since it detects and switches to heapsort for any killer inputs. https://drive.google.com/file/d/0B1-vl-dPgKm_T0Fxeno1a0lGT0E/view https://drive.google.com/file/d/0B1-vl-dPgKm_T0Fxeno1a0lGT0E...
    - lorenzhs 8y ago
      Thanks, I totally forgot about pdqsort! If I recall correctly, it's partially based on blockquicksort, but includes a lot of other improvements. It's a very interesting algorithm, much faster than introsort etc. However, I believe that IPS4o is still faster overall (I think I asked Sascha, one of the authors of IPS4o, about this a while ago, but I don't have any measurements at hand), even before accounting for IPS4o's parallel implementation. You should definitely check out both :)
  - hinkley 8y ago
    I think I need to swear off of involving myself in order of complexity conversations and just get back to doing useful work. "The difference between theory and practice is that in theory there is no difference." and as processors evolve that just becomes more and more true for complexity calculations. It's still a useful and helpful mental exercise but what matters is if I can do an operation cheaper and more reliably than you can. Order of complexity informs that decision but doesn't define it. Even a moderately sized C is proportional to log(n) for quite a lot of data sets most of us actually work with. Conversely, adding, subtracting or comparing two numbers of arbitrary precision (eg, bignum) takes log(n) time, not O(1) time. Very few algorithms we call < O(n) are implementable in less than O(n log n) as n -> ∞ Complexity analysis is step 2. Step 1 being admitting you have a bottleneck. But there are a lot of other steps after those, with a lot of challenging, specialized work.
    - lorenzhs 8y ago
      It all depends on your machine model. You're right in that the RAM model doesn't model the performance characteristics of real-world computers very precisely. That's why it's a model :) Other models exist that can be used to analyse various aspects of algorithms, e.g. the External Memory model (which can be applied to any level of the memory hierarchy, e.g. to quantify data transfer between cache and RAM). Or you can count the number of hard-to-predict branches, etc. We almost always assume that a machine word is large enough to describe the input size n. This usually implies constant-time operations on log(n) bits. Not doing so would clutter up notation and complicate analysis, and the whole point of using models is avoiding that where reasonably possible. I mean you could take this thinking to the extreme and say that as we live in three-dimensional space, the wire length to access more and more memory has to grow at least with the cube root of the size of the memory, because that memory needs to physically be stored somewhere at the end of the day. That's not helpful for analysing algorithms, though :)
      - hinkley 8y ago
        But for instance in a world where horizontal scalability is almost a given, we have to allow that the cost of sending a message between 2 arbitrary servers is going to be at least log(n) time, because if you build a star topology your entire server room would be wires. So if you're doing a distributed hash, the base cost of fetching two values to compare them is not only nothing to sneeze at, it is probably fundamental to how you solve the problem.
- comicjk 8y ago
  Example of the crazy optimizations that apply here: I once got a 20% speedup in a standard recursive search algorithm by abandoning the native function call stack and making my own search-specific stack data structure. Since these algorithms call the same function over and over, making the call stack do minimum work is actually significant.
- lmm 8y ago
  TimSort is an immensely complex sorting algorithm, full of magic numbers and difficult to analyse formally (e.g. the invariants it preserves are multi-line disjunctions). I'm not surprised there are still bugs to be found in it. I do think that issues like this make the case for using simpler, clearer algorithms even at a slight performance penalty.
- e12e 8y ago
  > Amazing there is still something to find in a sort algorithm. While more of an implementation detail, you might enjoy: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about... if you haven't seen it. Discussed at the time and later, eg: https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=14906429
0x0 8y ago
The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java 10.0.2 with an 'Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49'. Amazing! I wonder if this makes some web services vulnerable.. if the user can submit a just-so array of ints to be sorted? But it does seem like it would require uploading a really huge array (>4GB?)
- sleepychu 8y ago
  Crashing out of execution doesn't really seem like an actionable attack vector, unless that exception bubbles all the way to the application invocation.
  - mcherm 8y ago
    Causing a crash is an excellent vector for a denial-of-service attack.
    - alexeiz 8y ago
      If you can make your service allocate 10G of memory, it's already a denial of service attack.
    - vbezhenar 8y ago
      Usually unexpected exception results in a HTTP 500 response (or something similar) and few lines in the log. It does not result in stopped server.
    - ryeguy 8y ago
      It's an exception, not a crash.
- Insanity 8y ago
  Chances are you'll get an OutOfMemoryException first :)
  - 8y ago
willtim 8y ago
Not good that Java's sort still has bugs.
- wiz21c 8y ago
  I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.
  - elygre 8y ago
    The java bug (https://bugs.openjdk.java.net/browse/JDK-8203864 https://bugs.openjdk.java.net/browse/JDK-8203864) has some more information on the history, including a reference to an earlier paper from 2015 relating to the same problem. Apparently, the earlier paper had an error, so the implemented fix was not complete. Still intriguing, though!
  - pvg 8y ago
    It looks deceptively like it but 'kudos' is not plural of a kudo (or reference to some awesome thing Kudo once did).
    - basil-rash 8y ago
      Is it really not? The dictionary says otherwise, albeit by back-formation (as is the English way). https://www.merriam-webster.com/dictionary/kudo https://www.merriam-webster.com/dictionary/kudo
    - klmr 8y ago
      … and even if it were a plural the apostrophe would be misplaced.
  - willtim 8y ago
    What's amazing is how little understanding we seem to have over such critical widely-used code. Java opted for a complex and arguably unproven algorithm, so it was always a risk. We now have functional languages that are able to express provably correct sorting algorithms, so the bar is getting higher.
grillorafael 8y ago
Given that rho can vary with the input and is completely arbitrary value, shouldn’t be also called n? Memories on the subject are not great so might be saying bullshit in here
- phoe-krk 8y ago
  It shouldn't be called n because then `n log n` and `n log m` convey different meanings. In the first case, `n` is one and the same variable, where in the second, `n` and `m` are independent of each other. You can call it `m` or `rho` or whatever, just use a different variable.
  - ygra 8y ago
    Here, ρ is not independent of n, though
    - deleted 8y ago
      [deleted]
    - AstralStorm 8y ago
      Rho is always 1 to n as defined. In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.
    - ehsankia 8y ago
      It sort of is though. You can have a really large N with rho = 1, just like you can have a really small N with rho=N. They're orthogonal variables, and they both impact the run time.
- matharmin 8y ago
  In the worst case, rho is equal to n, and you get O(n log n). However, O(n + n log rho) gives a better description of how it performs on partially sorted arrays.
  - 8y ago
TeMPOraL 8y ago
How is it that the abstract is talking about "Java version" and "Python version" when discussing computational complexity? Aren't algorithms algorithms, independent of the language you're implementing them in?
- growtofill 8y ago
  From the article: > In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively.
- LeoPanthera 8y ago
  It’s taking about the implementations in the respective standard libraries, which are apparently different.
- deleted 8y ago
  [deleted]
- grillorafael 8y ago
  Yes. If the java have a different complexity it is a different algorithm. To the writers defense, they have to algorithm in pseudo code in the article
  - brazzy 8y ago
    > If the java have a different complexity it is a different algorithm. It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.
    - ehsankia 8y ago
      Right, like how Quicksort can be pretty different depending on how you choose the pivot. It's still Quicksort, but there's different variants.
      - grillorafael 8y ago
kieckerjan 8y ago
I am surprised to see the author of TimSort (Tim Peters) does not have a Wikipedia entry. Seems to me he has enough claim to (wiki)fame.
- saagarjha 8y ago
  It's probably just that nobody's gotten around to writing one.

204 points by pelario 8y ago

julienfr112 8y ago

Amazing there is still something to find in a sort algorithm.

lorenzhs 8y ago
Especially when targeting realistic machine models, there are a lot of things that are suboptimal about the classical sorting algorithms like quicksort or mergesort. For example, a quicksort with perfect choice of pivot will incur a branch miss with probability 50% for every element. That's not something classical complexity analysis measures, but on actual CPUs, branch misses have quite an impact (something like 10–15 cycles). Shameless plug for something I once built for a lecture to demonstrate this: https://github.com/lorenzhs/quicksort-pivot-imbalance https://github.com/lorenzhs/quicksort-pivot-imbalance For sorting algorithms that take the behaviour of modern CPUs into account, check out ips4o (https://arxiv.org/abs/1705.02257 https://arxiv.org/abs/1705.02257, code: https://github.com/SaschaWitt/ips4o https://github.com/SaschaWitt/ips4o) or for a simpler algorithm that's still much faster than quicksort in most cases, blockquicksort (https://arxiv.org/abs/1604.06697 https://arxiv.org/abs/1604.06697, code: https://github.com/weissan/BlockQuicksort https://github.com/weissan/BlockQuicksort). Note that both papers were published in the last two years :) Of course these algorithms are much more complex and error-prone to implement and use some additional memory, which may explain why they're not used in standard library implementations of popular languages.
- rthomas6 8y ago
  This is awesome!
- kjeetgill 8y ago
  Out of curiosity, what do you read/follow that makes stuff like this discoverable?
  - lorenzhs 8y ago
    I'm a PhD student in algorithmics / algorithm engineering, so I work with a lot of people who do stuff like this, even though my research isn't related to sorting. Super Scalar Sample Sort (which ips4o is based on) was co-authored by my advisor, Peter Sanders, and I re-implemented it a few years ago in modern C++ just for the fun of it. Turns out that was a lot nicer to read than the original code (which isn't public) and a bit faster, too. I put that on GitHub where the blockquicksort authors found it and contacted me and we traded some emails and made some improvements. Sometime later my advisor and two colleagues came up with an idea for in-place super-scalar sample sort, out of which eventually ips4o was born. So, uh, I guess I just work with the right people :) Sorry that I can't give you anything concrete. All of these papers were presented at ESA (European Symposium on Algorithms), though, so that's a good venue to follow. But beware, ESA has a theory track that's a lot bigger than the experimental track, and papers published there can be somewhat unapproachable ;)
    - kjeetgill 8y ago
      Ahh, that makes sense, thanks! I'd recently asked elsewhere 'I've always wondered is there a good mathematical representation of an algorithm that is useful for algebraic manipulation? Like producing a quicksort from bubble sort.' And got linked this paper [0]. This is only time I've heard the word 'Algoritmics' since that. Any interesting 'entry level' reads you could send my way? [0]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.2247&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45....
      - lorenzhs 8y ago
        Thanks for the link, that was fun to read (well, skim). I don't think the term 'algorithmics' appears very often in publications, it's more of an umbrella term for many things. The stuff we work in our group is sort of the practical side of theoretical computer science, in that our focus is on algorithms that can be efficiently implemented and don't just look good on paper. The methodology is called Algorithm Engineering, it's described quite well in https://en.wikipedia.org/wiki/Algorithm_engineering https://en.wikipedia.org/wiki/Algorithm_engineering. Apart from ESA's track B, the major conferences there are Alenex and SEA (Symposium on Experimental Algorithms). All three are open access. It's difficult to recommend anything in particular, not only because the scope is very broad, but also because most papers aren't written for a wide audience. Good writing is not something that academics optimize for (perversely, good writing can be seen as a negative point, in that if a paper is easy to understand, it may be rejected for being too simple), nor is it taught. Maybe something like https://github.com/papers-we-love/papers-we-love https://github.com/papers-we-love/papers-we-love could serve as a starting point?
- notriddle 8y ago
  You probably want to use pdqsort, since it detects and switches to heapsort for any killer inputs. https://drive.google.com/file/d/0B1-vl-dPgKm_T0Fxeno1a0lGT0E/view https://drive.google.com/file/d/0B1-vl-dPgKm_T0Fxeno1a0lGT0E...
  - lorenzhs 8y ago
    Thanks, I totally forgot about pdqsort! If I recall correctly, it's partially based on blockquicksort, but includes a lot of other improvements. It's a very interesting algorithm, much faster than introsort etc. However, I believe that IPS4o is still faster overall (I think I asked Sascha, one of the authors of IPS4o, about this a while ago, but I don't have any measurements at hand), even before accounting for IPS4o's parallel implementation. You should definitely check out both :)
- hinkley 8y ago
  I think I need to swear off of involving myself in order of complexity conversations and just get back to doing useful work. "The difference between theory and practice is that in theory there is no difference." and as processors evolve that just becomes more and more true for complexity calculations. It's still a useful and helpful mental exercise but what matters is if I can do an operation cheaper and more reliably than you can. Order of complexity informs that decision but doesn't define it. Even a moderately sized C is proportional to log(n) for quite a lot of data sets most of us actually work with. Conversely, adding, subtracting or comparing two numbers of arbitrary precision (eg, bignum) takes log(n) time, not O(1) time. Very few algorithms we call < O(n) are implementable in less than O(n log n) as n -> ∞ Complexity analysis is step 2. Step 1 being admitting you have a bottleneck. But there are a lot of other steps after those, with a lot of challenging, specialized work.
  - lorenzhs 8y ago
    It all depends on your machine model. You're right in that the RAM model doesn't model the performance characteristics of real-world computers very precisely. That's why it's a model :) Other models exist that can be used to analyse various aspects of algorithms, e.g. the External Memory model (which can be applied to any level of the memory hierarchy, e.g. to quantify data transfer between cache and RAM). Or you can count the number of hard-to-predict branches, etc. We almost always assume that a machine word is large enough to describe the input size n. This usually implies constant-time operations on log(n) bits. Not doing so would clutter up notation and complicate analysis, and the whole point of using models is avoiding that where reasonably possible. I mean you could take this thinking to the extreme and say that as we live in three-dimensional space, the wire length to access more and more memory has to grow at least with the cube root of the size of the memory, because that memory needs to physically be stored somewhere at the end of the day. That's not helpful for analysing algorithms, though :)
    - hinkley 8y ago
      But for instance in a world where horizontal scalability is almost a given, we have to allow that the cost of sending a message between 2 arbitrary servers is going to be at least log(n) time, because if you build a star topology your entire server room would be wires. So if you're doing a distributed hash, the base cost of fetching two values to compare them is not only nothing to sneeze at, it is probably fundamental to how you solve the problem.
comicjk 8y ago
Example of the crazy optimizations that apply here: I once got a 20% speedup in a standard recursive search algorithm by abandoning the native function call stack and making my own search-specific stack data structure. Since these algorithms call the same function over and over, making the call stack do minimum work is actually significant.
lmm 8y ago
TimSort is an immensely complex sorting algorithm, full of magic numbers and difficult to analyse formally (e.g. the invariants it preserves are multi-line disjunctions). I'm not surprised there are still bugs to be found in it. I do think that issues like this make the case for using simpler, clearer algorithms even at a slight performance penalty.
e12e 8y ago
> Amazing there is still something to find in a sort algorithm. While more of an implementation detail, you might enjoy: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about... if you haven't seen it. Discussed at the time and later, eg: https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=14906429

0x0 8y ago

The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java 10.0.2 with an 'Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49'. Amazing! I wonder if this makes some web services vulnerable.. if the user can submit a just-so array of ints to be sorted? But it does seem like it would require uploading a really huge array (>4GB?)

sleepychu 8y ago
Crashing out of execution doesn't really seem like an actionable attack vector, unless that exception bubbles all the way to the application invocation.
- mcherm 8y ago
  Causing a crash is an excellent vector for a denial-of-service attack.
  - alexeiz 8y ago
    If you can make your service allocate 10G of memory, it's already a denial of service attack.
  - vbezhenar 8y ago
    Usually unexpected exception results in a HTTP 500 response (or something similar) and few lines in the log. It does not result in stopped server.
  - ryeguy 8y ago
    It's an exception, not a crash.
Insanity 8y ago
Chances are you'll get an OutOfMemoryException first :)
- 8y ago

willtim 8y ago

Not good that Java's sort still has bugs.

wiz21c 8y ago
I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.
- elygre 8y ago
  The java bug (https://bugs.openjdk.java.net/browse/JDK-8203864 https://bugs.openjdk.java.net/browse/JDK-8203864) has some more information on the history, including a reference to an earlier paper from 2015 relating to the same problem. Apparently, the earlier paper had an error, so the implemented fix was not complete. Still intriguing, though!
- pvg 8y ago
  It looks deceptively like it but 'kudos' is not plural of a kudo (or reference to some awesome thing Kudo once did).
  - basil-rash 8y ago
    Is it really not? The dictionary says otherwise, albeit by back-formation (as is the English way). https://www.merriam-webster.com/dictionary/kudo https://www.merriam-webster.com/dictionary/kudo
  - klmr 8y ago
    … and even if it were a plural the apostrophe would be misplaced.
- willtim 8y ago
  What's amazing is how little understanding we seem to have over such critical widely-used code. Java opted for a complex and arguably unproven algorithm, so it was always a risk. We now have functional languages that are able to express provably correct sorting algorithms, so the bar is getting higher.

grillorafael 8y ago

Given that rho can vary with the input and is completely arbitrary value, shouldn’t be also called n? Memories on the subject are not great so might be saying bullshit in here

phoe-krk 8y ago
It shouldn't be called n because then `n log n` and `n log m` convey different meanings. In the first case, `n` is one and the same variable, where in the second, `n` and `m` are independent of each other. You can call it `m` or `rho` or whatever, just use a different variable.
- ygra 8y ago
  Here, ρ is not independent of n, though
  - deleted 8y ago
    [deleted]
  - AstralStorm 8y ago
    Rho is always 1 to n as defined. In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.
  - ehsankia 8y ago
    It sort of is though. You can have a really large N with rho = 1, just like you can have a really small N with rho=N. They're orthogonal variables, and they both impact the run time.
matharmin 8y ago
In the worst case, rho is equal to n, and you get O(n log n). However, O(n + n log rho) gives a better description of how it performs on partially sorted arrays.
- 8y ago

TeMPOraL 8y ago

How is it that the abstract is talking about "Java version" and "Python version" when discussing computational complexity? Aren't algorithms algorithms, independent of the language you're implementing them in?

growtofill 8y ago
From the article: > In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively.
LeoPanthera 8y ago
It’s taking about the implementations in the respective standard libraries, which are apparently different.
deleted 8y ago
[deleted]
grillorafael 8y ago
Yes. If the java have a different complexity it is a different algorithm. To the writers defense, they have to algorithm in pseudo code in the article
- brazzy 8y ago
  > If the java have a different complexity it is a different algorithm. It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.
  - ehsankia 8y ago
    Right, like how Quicksort can be pretty different depending on how you choose the pivot. It's still Quicksort, but there's different variants.
    - grillorafael 8y ago

kieckerjan 8y ago

I am surprised to see the author of TimSort (Tim Peters) does not have a Wikipedia entry. Seems to me he has enough claim to (wiki)fame.

saagarjha 8y ago
It's probably just that nobody's gotten around to writing one.