3 ms·
>My most successful application speedup ever... > people tend to not even know how many objects they create in many dynamic languages One of my biggest speedup
by bane 12y ago
>My most successful application speedup ever...
> people tend to not even know how many objects they create in many dynamic languages
One of my biggest speedup success stories was an internal inventory reporting tool for a large-ish online retailer. The code was written in Perl, with huge amounts of data aggregation happening in memory and using loads of Perl hashes pointing to other Perl hashes point to others (and turtles all the way down). On small subsets of the data, it would run for 4 or 5 hours then spit out some graphs -- this was acceptable performance for daily reports. But as the site grew, it started taking 8 hours, then 10 hours and then finally crashing when the system simply ran out of memory.
So I did a simple conversion, all the hashes pointing to hashes etc. into arrays pointing to arrays. Pretty simple in the code, only a few lines of code here and there and a couple functions to map hash keys into array indexes.
The next day the entire inventory system did a run (with this one change) and finished in 10 minutes and AFAIK they still use that same system even though the site and user activity has grown a hundredfold.
The developer (self-taught) of the original code asked why this worked. I walked him through the big-O complexity of arrays vs. hashes, and more importantly the amount of stuff the hash type was dragging around through memory. There used to be a fantastic site with visualizations of all the perl datatypes and we sat down and started counting bytes until he understood the difference.
- dylanrw 12y agoIt's excellent that you'd do that for him, and he was curious/receptive enough to ask and step through it all. So many times I've seen people stay ignorant to save face.
- bane 12y agoHe's a great guy, really open minded and always learning. He taught me tons also, and he's moved far beyond where I could ever hope to technically.
- vidarh 12y agoI catch myself just throwing everything in inappropriate data structures myself these days, because the hardware lets me get away with it, and many recent languages makes hashes so ridiculously simple to work with and don't provide much more than that + arrays. I don't like it, though.
- bane 12y agoI guess that's kind of the problem though right? The hardware lets you get away with it, only until it doesn't. Then if you don't know the fundamentals, you're in trouble or you end up spending an inordinate amount of time and money trying to spread the task across dozens of systems in a couple racks of in some datawarehouse somewhere.
- vidarh 12y agoAbsolutely. And then the blame often gets shifted to things like the language or framework and rewrites start being bandied about instead of analysing algorithm usage because the problem often isn't apparent when looking at profiles etc. unless you're used to looking for exactly this class of problems. And people start talking about "Big Data" and Hadoop and similar when their data are really middle of the tree and can easily fit on a single server..
- bane 12y agoI'm at a company now where our default deployment is something like 6 fairly heavy VMs. You can jam it all into 4 lighter VMs and service a single user (which is what we do for testing on our laptops) and it runs..."ok". Looking at what they're actually doing, basically a few postgres or solr requests, file serving and generating a some web pages...the data for one of our larger deployments barely breaks 1 GB when dumped out of the databases (It doesn't handle more than 100 users at a time)...it should be running cleanly off of a $699 mid-range all-in-one desktop from Costco and have enough headroom for 5,000 more users. Yet somehow between all the framework, JVM and various other nonsense, there's murmers about moving that system to a more web-scale infrastructure because of all the performance issues we're seeing. Everytime somebody uploads some content to the server 4 of the VMs peg out their cores for several seconds. As I look around in engineering meetings at all the fresh young engineers working on this stuff, nobody seems to think this is a problem. On the client side the problem is even worse, constrained to the 1990s era performance we're stuck with inside of browsers. Machines capable of crunching billions of calculations per second, and putting tens of billions of bytes into main memory are brought to their knees dragging and dropping a half-dozen items in a GUI (something my Commodore 64 could actually handle) or running two programs at once, something my Amiga 500 could do. It's bad and it makes me feel bad. I think growing up when computers were basically terrible has broken me to where things that young engineers think is cool and amazing I'm finding more and more disappointing...it's not that old computers were great, it's that modern computers aren't but they should be. The future is now, and it kind of sucks.
- zak_mc_kracken 12y agoMaybe I'm not familiar enough with Perl's implementation of "Hash", but if it's what I expect a "Hash" to be, access time is constant. What kind of data structure was actually in play there?
- bane 12y agoHashes end up O(n) not O(k) in worst case scenarios. Arrays are guaranteed O(k). But that's also a simplistic view of how they work. Hashes, by necessity are far more complex than arrays. As you use them, there's lots more overhead involved that can cause things like cache misses, memory doubling when growing, rehashing etc. More importantly, hashes need to store both the key and value pair. Arrays just need to allocate memory and user pointer arithmetic to offset from the array start location to arrive at each index. If you think of an Array as just a Hash with numbers for the keys, Arrays "store" the keys basically for free. While even a hash with integers for the keys has to store 4 bytes for each key (on 32-bit implementations). When hashes hit some utilization percentage, Perl (and any sane language) constructs a new, larger hash, then moves all the keys and values over (requiring all the keys to be rehashed again). When Perl lists get need to grow, a new array is constructed and all the pointers from the old one are copied over to the same indexes in the new one, no rehashing is needed and no values need to be copied. Destroying the old array and returning it to memory is also easier and faster than destroying the old hash. Hashes are also much more aggressive in resizing. I believe Perl Arrays resize only once they're 100% consumed, but hashes, in order to prevent collisions, have to resize once they hit something like 50% utilization, and they grow by doubling their space leaving lots of unused entries in the hash (I could be wrong on the exact details, but the ideas is the same). Here's the illustrations of Perl's datatypes. It really clears up lots of mysteries about how Perl works internally. http://www.cpan.org/modules/by-module/LWP/GAAS/illguts-0.09.pdf http://www.cpan.org/modules/by-module/LWP/GAAS/illguts-0.09.... The relevant portions are "AV" and "HV". I haven't read this in years, but at one point I had large chunks of it memorized and could hand count the number of bytes in memory I expected a Perl datastructure to take up and be fairly accurate with it. For sake of comparison it's useful to run the following code. An Array version for($i=0;$i<1000000;$i++) { $av[$i]=$i; } system("pause"); And a Hash version for($i=0;$i<1000000;$i++) { $av{$i}=$i; } system("pause"); and check the memory usage for both. On my system, the first one consumes about 35MB of memory. The second one takes about 216MB of memory and is a hair slower. Now suppose each entry in each structure pointed to another array or hash respectively each with a million entries, and each of those in turn did the same. The memory growth of the array version is going to be much slower than the hash version. This holds true for most languages, they implement their arrays, lists and hashes similarly and have similar issues for all of them.