The big-load anti-pattern
lemire.me
lemire.me
Really good advice - this is a hard earned lesson for many folks. I've worked with quite a few data scientists who were brilliant at experimental design but not necessarily experts in the field of comp sci. Their relatively simple python scripts would run nice and fast initially. As time passed and the organization grew, their scripts would start to run slower and slower as the datasets scaled and swapping to disk started occurring, etc. In some cases they would completely lock up shared machines, taking a good chunk of the team offline for a bit.
Anyway, Daniel Lemire's blog is a fantastic resource. I highly recommend taking a look through his publications and open source contributions. I was able to save my employer a lot of money by building on time series compression algorithms [1] and vectorized implementations [2][3] that he has provided.
[1] Decoding billions of integers per second through vectorization https://onlinelibrary.wiley.com/doi/full/10.1002/spe.2203
Once I did it with a large RDF (XML) that was a list of books. Initially I loaded and processed it in Perl with XML::Simple, but XML::Twig let me deal with things one record at a time.
The other time I had a large Java linked list holding objects, where I grabbed the head, processed it, and then shrunk the list (removeFirst()) as I proceeded (I probably could have optimized the loading even more).
As a one-person project, punting on the big load optimization worked for me, as I had a working program even before optimizing. If it was a larger project, what time would be best to optimize might have differed.
I can see MIT/permissive licenses being less attractive than usual in an environment like that, because the author might perceive reduced chance of reaping rewards (versus aiding competitors) from publishing components.
If improvements led to greater-than-zero reward for publishers and consumers alike, though (as enforced by copyleft approaches), then perhaps the results would be different. All conjecture, really.
The problem of "as the organization grew,..." is the problem you want to have. 90% of organizations instead have the problem "As we failed to get any interesting results or any funding, and our contributors started drifting away to other projects,..." and sometimes the reason they have that problem is precisely because the initial contributors were too concerned about doing things "the right way" and weren't satisfied with "relatively simple Python scripts [that] run nice and fast initially".
When your limiting factor is programmer effort, there are two kinds of systems: the kind that runs as slowly as the users and developers can tolerate, and the kind that people don't use because it lacks the functionality they want, functionality that some other system has. Probably a slower one.
Of course you should make things go as fast as you can, and performance can be critical not only for ergonomics but also for the ability to iterate rapidly, and sometimes the performance is the functionality, but when you find yourself facing down the shitty performance of "founder code" that locks up shared machines, don't fall into the trap of wishing that the people had done it right in the first place, before "time passed and the organization grew". In the startup graveyard there are nine other groups who tried to do the same thing, but couldn't quite get it right. Some of them probably had damn fast code, which you aren't looking at, because their organization never grew.
And I say that as someone who spent a fair bit of the last week looking at assembly language and thinking about compiler optimization tradeoffs.
This is battle-worn experience and I will absolutely die on this hill. Relational databases JUST WORK.
The only exception is when you need to do complex ML on big data, in which case, take your pick from Apache Spark, Dask, or some similar framework. Hopefully these will be increasingly supplemented by in-database ML going forward, so that there is no reason to ever leave the database.
If you've got to sort (or writing an alternative is too time-consuming), do it after eliminating as much data (variables, records) as possible.
Hash tables (or other comparable tools such as btrees or Bloom filters) can be used for dataset comparisons or key-value lookups.
Arrays can be used to keep a runnning count of top-n records (this may need to be sorted on insert, though comparing largest/smallest entry can mitigate this).
Random sampling is very often as good as complete processing, especially where the goal is to find the general characteristics of a dataset rather than an exhaustive view or precise tabulation. Even in accounting and financial operations, sampling methods may be acceptable (see for example, mechanical copyright royalties on performance of recorded music broadcasts, or advertising and circulation rates in publishing). It's fairly staggering how clearly a small sample (as few as 30 records, often only a few hundred or thousand) can describe an immense dataset (millions or billions of entries) with reasonable accuracy, so long as it is randomly selected. And if the first sample seems off, try pulling a few others and seeing how they compare. (Effectively: Monte Carlo method.)
The place where sampling methods break down most is in iterative-calculation forecasts (e.g., weather modeling), where larger aggregations (typically measured as datapoints over both area and time) greatly reduce accuracy. Though even with very precise reporting density, today's weather forecasts tend to be limited to 7--10 days. Sometimes randomness simply wins.
Honored and wise Morbius, I humbly beg to differ; top-N record arrays never need to be sorted on insert, because a binary heap is 25 lines of code. Then all you need for top-N is:
for record in input_file:
if record <= aMinheap.minimum:
continue
aMinheap.extract_minimum()
aMinheap.add(record)
I was thinking quickselect was even faster when your data does fit in RAM, but I can't see how that could be true, even though it's linear time: if you have a million records, then the first partitioning step of quickselect will examine all of them (doing one comparison for each), the second partitioning step will examine on average half of them, and the third partitioning step will examine on average somewhat more than a quarter of them (because the expected size for the result of the second partitioning step is more than 250,000 records), and so we end up doing something like e comparisons per record on average rather than 1.
But, with the running-candidate-set approach you suggested, if the million records are in random order, after we're past the first 1000 records, we do only a single comparison for at least 90% of the remaining records (because they're less than the top 100 from the first 1000), and after we're past the first 10,000 records, for at least 99%. So if we did 8000 comparisons in the first 1000, then inserted 900 of the next 9000 records for another 7200 comparisons (plus 9000 comparisons to reject the other 8100), and then another 900 of the next 90,000 records (plus 90,000 initial comparisons), we're at 121,400 comparisons for the first 100,000 records, 1.214 comparisons per record. So, for a small top-N query, quickselect loses the race before it's finished with its second partitioning step. Or am I overlooking something?
I think my first iteration used bubble sort. That was still faster than a sort | head script, by a lot.
(I think I later improved on that, possibly by retaining min/max records.)
Even in awk, and even when choosing large values for n (e.g., thousand or tens of thousands of records), this easily beat the sort utility in cpu time, wall-clock time, and memory usage, for many millions of input records.
(Most of my coding tends to be hackish and brutish. Algorithms are not my strong suit.)
Haha! Gotta get Barack Obama to give you some algorithms lessons.
Thinking about it further, the initial heapify phase of heapsort is linear-time, and it's the later heap-popping phase that takes most of the runtime; if the command-line `sort` used heapsort for in-memory data, maybe `sort | head` would have been competitive or even faster? At least for n>32 or so? The usual algorithm for `sort` is mergesort, because that makes it perform acceptably for things that don't fit in RAM, but mergesort has to do most of its work before it can start producing output.
This is important, but I think sometime people struggle with this sort of thinking. I struggled to explain a similar concept to a junior engineer recently. He was very keen to try to optimize part of a process that wasn't the bottleneck. I tried a couple approaches, like benchmarking various parts under different conditions, modeling it to calculate how speeding up different components would take.
I wasn't convincing, unfortunately, so he implemented some changes that sussessfully sped up one part but didn't improve end to end performance. I think sometimes you need to see it with your own eyes.
I realize over the years that the 'load everything' thing is often linked to lack of understanding of machine limitations and little training in stream-processing and how efficient and scalable it is.
I'd blame maths teaching that focuses on the abstract operation (full formula) and their 'implementation' past simple examples. Or I'd blame Excel as the gateway drug to numerical computing. But mostly, it's probably 'just' that not that many people happen to encounter data 'that' big (yet it's not 'big' data) and when they do they're often not helped in finding 'progressive' solutions. Running variant/avg isn't hard to understand but you must know it exists... Basic stream processing can be achieved with not too much changes (depending on the algorithms, of course). Simple indexes can be quite easy to build... But often we sell them 'you need to go full DB' or 'this is a job for hadoop or infrastructure-nightmare-tool-of-the-day'. Not everyone points you to https://ujmp.org/ with sparse/dense 1d/2d/3d matrix structures and operations and different storage options (disk-backed, etc...).
Most of the time I meet data scientists in difficulty, after 1h of explaining how I do X using roaring bitmaps or sparse structures or after 1h spent building a file/field index using very robust (old) libraries in their language/environment of choice, I see them build pretty solid and scalable pipelines...
- Generate jobs only containing metadata and distribute those jobs to workers. There the actual data that is required for that specific job is queried on the fly from the db.
For a similar task however we later switched to the following strategy:
- Load all data to be processed at once, use all sorts of distributed transformations and aggregations on the full data set and do the splitting at the end of the workflow.
The reason why we switched? The only real reason was that it seemed more the "Big Data style" to do stuff. With the first approach we actually would not need all the fancy Spark functionality right? We would only abuse the framework for a fancy way to distribute mostly independent workloads.
However, I very much regretted that decision later as it made our life harder in many ways. For example, I could easily execute and thus debug one of the former jobs locally within a minute. Try that when the workflow is designed in a way that it needs to load several gigabytes before applying any logic. To be fair, the total load on the db was somewhat lower using the second approach, but that just wasn't worth it.
I see the same mistakes done with JSON nowadays.
Basically, if you don’t need the DOM in its entirety, don’t parse it all.