Cydia 1.1.29 is a performance release


Avoid downloading translations that will 404

While I currently believe there to be not a single repository in the wild which uses this feature (which makes me sad, but like: it isn't as if my repository does this currently either :/), Cydia supports package names and descriptions to be translated into different languages.

As some people noticed, the new 64-bit builds of Cydia did all this even more "correctly" and would try to download lots of translation files, making refreshes slower. As is expected, someone was like "why not just remove that feature", which seemed like a really wrong thing to do :/.

Instead, I've fixed a feature of APT which is supposed to filter "optional" files from being downloaded to work with repositories that do not have the list of files that would normally be in the Release file (the behavior in this case is it doesn't download them: if you have such a repository and you want translations, fix your Release file).

Correct package catalog loading

Did you know that, unlike either std::vector or NSMutableArray, when CFMutableArray says "capacity" they don't mean "this is how much can be stored before the next allocation" but instead "this is how much can be stored in this array: it will never get larger"? Well, I didn't :(. Apparently, neither did Microsoft ;P. While working on the next issue, I discovered this one, and was pretty shocked.

This might explain some of the weirder stuff people have reported while using Cydia recently: cases where some packages show up, but others do not, which no one could replicate and which seems to just go away: when Cydia starts without a catalog, it would set its capacity to 16k packages, and then up it by 1024 every refresh... but there are many tens of thousands of packages in just the default repostories, so it could take some time for Cydia to "warm up" and see all of them, after which it would just work :/.

Then again, it might not... this is just such weird behavior for an array to have... it even claims appending to the end of a full capacity-limited array results in "undefined behavior". Some people report that the array gets bigger? Honestly: I haven't tested it, as I found this while determining I needed to move to something more like std::vector anyway. I think it is a really interesting bit of trivia, though, for those of us bothering to read the advanced release notes for a Cydia performance release ;P.

Improve package catalog sorting performance

Cydia has the crazy challenge of having to do locally on your device what a centralized, curated, philosophically-annoying (I shake my fist at thee, Apple!) solution would do on a server: update a list of many tens of thousands of packages, sorting the result not just alphabetically, but in the locale-sensitive way that users expect.

I designed for Cydia what I think is a pretty epic solution to this problem, involving adapting radix sort to work on strings using crazy transformations, doing multiple passes followed by a "fixup" insertion sort. It is the kind of algorithm that really demonstrates why all developers should have a strong algorithm background, as some day you will need one of these. I give talks about this sorting algorithm to college-level computer science classes ;P.

However, it has required some "calibration" over the years, and apparently it wasn't up to the challenge of sorting Chinese (Traditional) in "stroke order"; this ordering was a feature that was highly requested by Chinese users, and was added to Cydia as of iOS 8, but caused the radix sort passes of my algorithm to require too much later fixup using insertion sort. There's still some improvements to be made here in the radix pass, but when this performance issue was reported yesterday, I had a better solution.

I actually had already designed Cydia's sort ordering to be capable of taking advantage of a "sort cache", reusing the results of previous executions of Cydia to get "close enough" instead of using radix sorts. This, combined with some algorithmic improvement to the insertion sort passes, combined with moving more of the algorithm to C++ (I deeply regret how much Objective-C and even CoreFoundation is in Cydia...), has drastically improved the performance of loading Cydia, at least for Chinese.