I/O is no longer the bottleneck

If you read 1,000,000 random bytes (~1 Mb) scattered across a huge file (let's say you're fetching from some humongous on-disk hash table), it will to a first order be about as slow as reading 4 Gb sequentially. This will incur the same number of page faults. There are ways of speeding this up, but only so much.

Although, I/O is like an onion of caching layers, so in practice this may or may not hold up depending on previous access patterns of the file, lunar cycles, whether venus is in retrograde.

The wondrous thing about modern CPU architectures (e.g. Zen3), though, is all the PCIe lanes you get with them. If you really need high random IOPS, you can now cram 24 four-lane NVMe disks into a commodity server (with PCIe M.2 splitter cards) and saturate the link bandwidth on all of them. Throw them all in a RAID0, and stick a filesystem on them with the appropriate stripe width, and you'll get something that's only about 3x higher-latency for cold(!) random reads, than a read from RAM.

(My company provides a data-analytics SaaS product; this is what our pool of [shared multitenant, high concurrency] DB read-replicas look like.)

Hilariously meanwhile, RAM has become significantly slower compared to CPU performance, i.e. you spend a disproportionate time to read and write to memory, so despite RAM is faster, CPU is way faster.

Which means I/O remains a bottleneck...

What we would really benefit is storage which is efficient in small (cpu cache line) size IO

You're probably also right their multiple test runs resulted in the OS caching data, and a lot of the test runs may have just been testing in-memory performance instead of raw storage I/O performance.

Regardless, the concurrent approach would be 90% the same as the single thread approach, leaving it for a good “after the fact” question, assuming the candidate still has time.

Nope, the GIL will make that useless. You need to actually implement the tight loops in C/C++ and call that with batches of data to get benefits from threading.

An obvious, but more expensive optimization would be to use a process pool. Make sure that all the objects you pass around are serializable.

Python makes optimization much harder than it should be. I hope the GIL gets the hammer at some point, but that seems to be a huge task.

Emery Berger has a great talk [1] where he argues that it is mostly pointless to optimize python code, if your program is slow, you should look for a properly optimized library to do that work for you.

1: https://www.youtube.com/watch?v=vVUnCXKuNOg

On my machine, the base script pretty reliably takes ~10s:

    Reading   : 0.1935129165649414
    Processing: 9.955206871032715
    Sorting   : 0.0067043304443359375
    Outputting: 0.01335597038269043
    TOTAL     : 10.168780088424683

    counts = collections.Counter(chain.from_iterable(map(str.split, map(str.lower, content))))

    Reading   : 1.1920928955078125e-06
    Processing: 8.863707780838013
    Sorting   : 0.004117012023925781
    Outputting: 0.012418985366821289
    TOTAL     : 8.880244970321655

You won't get a 10x gain out of that though.

That said, the OP's article is correct in that straightforward idiomatic implementations of this algorithm are very much compute bound. The corollary is that eng work put into optimizing compute usage often won't be waisted for programs processing disk data (or even network data with modern 10Gb fiber connections).

I installed a DB-Server for a Customer around 2years ago, in a DC near him with 16 cores 48GB Ram and ~6TB -> 12 SSD, vDevs mirror with 2, and Stripe over the mirrored vDevs (kind of a Raid10 but zfs), compression zstd (1GB could be compressed down to ~200MB so 5 times less reading/writing, and in theory ~30TB of pure DB-Data, 20TB realistic, remember never fill a zpool over 72%) record-size 16kb (postgresql). After 3 month the machine was paid (compared to the "cloud"-price) and the performance kind of 10-12 times higher.

Called the customer about a two month ago and he said the DB-Server is still to fast and maybe he wants another one who uses less power... ;)

If you look further at the count-words article you linked, I do have profiling graphs and bottleneck analysis.

Note that the interview questions I ask are open-ended, not trying to trick or trap people into giving the "wrong" answer. I like to have more of a discussion to see how they think about the problem, what data structures they'd use, how they'd profile, and so on.

Hah! I mean, if you can truly prove a business benefit by improving performance, I’m sure that you’d have a good shot at a promotion. Thing is it’s actually quite difficult to do so, and in the likely chance you cannot it just looks like you squandered a bunch of time for no reason.

It depends if this kind of optimization is valuable to the organization. Often times it's not. Spending money and time to save money and time is often viewed as less efficient than generating more revenue.

Imagine a foo/bar/widget app that only serves 20B people (obvious exaggeration to illustrate the point) and is only necessary up to a few hundred times per day. You can handle that sort of traffic on a laptop on my home router and still have enough hootzpah left to stream netflix. I mean, you are Google, and you need to do something better than that [0], but the hardware for your project is going to be negligible compared to other concerns unless you're doing FHE or video transcoding or something extraordinarily expensive.

Walk that backward to, how many teams have 20B users or are doing extraordinarily expensive things? I don't have any clue, but when you look at public examples of cheap things that never got much traction and probably had a suite of engineers [1], I'd imagine it's not everyone in any case. You're probably mostly looking at people with enough seniority to be able to choose to work on core code affecting most services.

[0] https://www.youtube.com/watch?v=3t6L-FlfeaI

[1] https://killedbygoogle.com/

Yes, I occasionally saw people get highlighted for making optimizations like "this saves 1% in [some important service]". When you're running millions of machines, 1% is a lot of machines. However, it's also likely the case that the easy 1%s have already been found...

You are hereby placed on a Performance Improvement Plan, starting tomorrow. On the off chance you'll come out of the other end still employed, keep in mind that your manager isn't being stupid by forbidding such 'optimizations', they're just following orders."

But I guess you could avoid that using eg. io_uring.

On a modern gen4 NVMe, I routinely get 7 GiB/s. gen5 is supposed to double that (as soon as manufactures get "enough" money out of gen4 given PCIe4's extremely short life compared to gen3's extremely long one.)

There was a time not long ago (maybe still) where highly scaled up, many core (40+) Intel CPUs could not match that getting from DIMMs into L3 for just 1 core (as per his interview problem). So, we are indeed moving into an era where "IO" from the primary persistent device is indeed no worse than IO from DIMMs, at least in bandwidth terms. DIMMs still have much better latency and the latency-BW ambiguity has been observed elsethread.

EDIT: I should clarify, to connect my text with your comment, that the real cost of (1-core, uncontended) allocation is also more "populating/mapping the cache" with copies, not just "allocation" in itself.

It is, but on both kind of drives you'll want to dispatch at least a couple of requests at once to get better performance. In the memory-mapped case, that means using multiple threads.

In addition, you might also want to call madvise(MADV_RANDOM) on the mapping.

No it’s not. At least not with modern SSDs or NVMe storage.

Even at 100 MB/s, a spinning disk in sequential mode is doing 100 x 1024 / 4 = 25,600 IOPS (assuming a standard 4K per operation).

Even consumer grade NVMe hardware gets 5-10x of that for random workloads.

Memory-mapped IO means you're only giving the SSD one request to work on at a time, because a thread can only page fault on one page at a time. An SSD can only reach its peak random IO throughput if you give it lots of requests to work on in parallel. Additionally, your test was probably doing small writes with all volatile caching disallowed, forcing the (presumably consumer rather than enterprise) SSD to perform read-modify-write cycles not just of the 4kB virtual memory pages the OS works with, but also the larger native flash memory page size (commonly 16kB). If you'd been testing only read performance, or permitted a normal degree of write caching, you would have seen far higher performance.

https://github.com/koraa/huniq

Edit: I had no idea that awk was so fast, and I suspect that only parallelization would beat it. but I agree with the others that the main bottleneck is the `sort | uniq` for results1.txt

  # https://stackoverflow.com/a/27986512 # count word occurrences
  # https://unix.stackexchange.com/a/205854 # trim surrounding whitespace
  # https://linuxhint.com/awk_trim_whitespace/ # trim leading or trailing whitespace
  
  time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | sort --buffer-size=50M | uniq -c | sort -hr > results1.txt
  real 0m13.852s
  user 0m13.836s
  sys 0m0.229s
  
  time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | awk '{count[$1]++} END {for (word in count) print count[word], word}' | sort -hr > results2.txt
  real 0m1.425s
  user 0m2.243s
  sys 0m0.061s
  
  diff results1.txt results2.txt
  109,39133c109,39133
  # many whitespace differences due to how `uniq -c` left-pads first column with space
  
  diff <(cat results1.txt | awk '{$1=$1};1') <(cat results2.txt | awk '{$1=$1};1')
  # bash-only due to <() inline file, no differences after trimming surrounding whitespace
  
  cat results1.txt | awk '{ sub(/^[ \t]+/, ""); print }' | diff - results2.txt
  # sh-compatible, no differences after trimming leading whitespace of results1.txt
  
  # 13.836 / 2.243 = ~6x speedup with awk

But really, I disagree because I've frequently saturated massive IOPS. I/O is still the bottleneck. The article pretty much immediately excludes network I/O, which is in many cases more common than disk I/O. Even so, tiny single-threaded programs reading words one-at-a-time are obviously not going to be I/O constrained with modern disks. For these types of programs, I/O hasn't been a bottleneck in a long, long time, and I'd actually be surprised to hear candidates suggest otherwise.

"Lowercase word count" is a surprisingly difficult case in this regard, because you need to check and potentially transform each character individually, and also store a normalized form of each word. Probably some smart SIMD lowercase function could help here but I don't think any language is going to offer that out of the box. It's also defined in a way I think detaches a bit much from real-world issues - it's handling arbitrary bytes but also only ASCII. If it had to handle UTF-8 it would be very different; but also if it could make assumptions that only a few control characters were relevant.

I have written a small script in python that does something similar. I have a word list with 1000 words and I check the presence of the words. Here is the thing. For every word I go through the entire file. So lets say I scan the file one thousand times. In fact I did something more complicated and ended up going 6000 times over the original file and yet it still took only three seconds. If all these scans had to reread the file it would take forever.

I'm curious what a multi thread(multi process for python due to GIL?) comparison would be. Obviously people aren't doing this by default though, so the author's point still stands.

(a quick glance at the C version tells me all I need to know with the scanf, strdup, etc. This is sorta like those C vs Java benchmarks which boil down to the fact that the default (glibc/etc) C malloc() isn't really optimized for perf, and what your really bench marking is how terrible it is for frequent tiny allocations. I think there _IS_ a diffrence between the code written by someone who lives C in a system programming context, and people who dabble in it from a higher level language.).

PS: Say using a hash to track a words frequency, likely works OKish but the need to keep it small, while still avoiding collisions would cause problems if the algorithm were parallelized in a long running system (rather than batching, where you would just run each thread against its own copy of the frequency tables, and then merge them at the end). But I'm still fairly certain that "your doing it wrong" if the overall algorithm can't run at a significant fraction of main memory bandwidth.

However one thing I found out a few years ago is that old data can be slow to read as a lot of error correction kicks in. Additionally a lot of fragmentation at the operating system level in Windows has quite a bit of overhead. It can seriously degrade performance to about 50MB/s sequential reads. In practice defragmentation/rewriting of certain high write files may be necessary on SSDs because Windows read performance degrades at high levels of fragmentation.

Correct. And there are actually two layers of fragmentation to worry about: the traditional filesystem-level fragmentation of a file being split across many separate chunks of the drive's logical block address space (which can be fixed by a defrag operation), and fragmentation hidden within the SSD's flash translation layer as a consequence of the file contents being written or updated at different times.

The latter can often have a much smaller effect than you might expect for what sounds like it could be a pathological corner case: https://images.anandtech.com/graphs/graph16136/sustained-sr.... shows typically only a 2-3x difference due to artificially induced fragmentation at the FTL level. But if the OS is also having to issue many smaller read commands to reassemble a file, throughput will be severely affected unless the OS is able to issue lots of requests in parallel (which would depend on being able to locate many file extents from each read of the filesystem's B+ tree or whatever, and the OS actually sending those read requests to the drive in a large batch).

May reduce wall-clock time but increase total compute time (and so also power). It's less an optimization than a tradeoff.

> please stop malloc'ing for each token

It doesn't, only when it gets put in the map. (And while the particular allocation could be smaller, something guaranteed to represent a specific arbitrary-length string has to be put in the map, which is going to malloc.)

> prealloc map for found tokens (better to just allocate room for 200k words).

Has no meaningful effect on performance.

> SIMD would optimise your inner-loop quite a lot.

No, as pointed out elsethread, it's a measurable boost but nowhere near the 10x you need to make the main claim (I/O not the bottleneck) be wrong. Not even 2x.

> `word = append(word, c)` <= this is very slow

Has no meaningful effect on performance.

Perhaps you should read the whole post.

SATA SSDs are limited to 550MB/s.

PCI-E 3.0 SSDs more like 3500 MB/s.

PCI-E 4.0 SSDs are 7000MB/s.

All of these are at consumer level pricing, you can get 2TB of PCI-E 4 from Western Digital for £130 at the moment, usually about £180. The issue is sustained writes more than reads for consumer verses enterprise drives where the speed drops off due to a lack of SLC caching and lack of cooling and TLC/QLC which is slower for sustained writing.

The example given is very much a consumer level device and not a particularly quick one by today's standards. You can also expect much faster reads cached than that on a DDR5 system I suspect.

The main difference is in write performance: consumer SSDs use SLC caching to provide high burst write performance, while server SSDs usually don't and are optimized instead for consistent, sustainable write performance (for write streams of many GB).

Server SSDs also usually have power loss protection capacitors allowing them to safely buffer writes in RAM even when the host requests writes to be flushed to stable storage; consumer drives have to choose between lying to the host and buffering writes dangerously, or having abysmal write performance if the host is not okay with even a little bit of volatile write caching.

whether o(m log m) is bigger or smaller than o(n) depends on the relationship between n and m

in the case used by another poster in this thread, concatenating some large number of copies of the bible, m is constant, so o(m log m) is o(1)

in another possible case where the corpus is generated uniformly randomly over all possible words of, say, 20 letters, though in theory o(m log m) is o(1), over a practical range it would be o(n log n)

more typically m is proportional to some power of n depending on the language; for english the power is 'typically between 0.4 and 0.6'

as it turns out o(√n log √n) is less than o(n)

a totally different issue is that big-o notation doesn't always narrow down where the bottleneck is even if you calculate it correctly because n is never arbitrarily large and so the bottleneck depends on the constant factors

The author’s point is that if we have two different inputs A and B, and A is sufficiently smaller than B, then the runtime of B will dominate the program. This would be true even if we have to operate on A with a very slow algorithm.

For example suppose you have some extreme scenario where you have to do three coloring on A and then find the minimum value of B. The runtime would be O(2^A) + O(B). Just plug in numbers and you can see that if B > 2^A then B takes longer even though that algorithm is much faster. If you suppose B is always much larger than 2^A, then B is your bottleneck.

i hope you are doing well

The problem is dealing with an asynchronous filesystem API provided by the kernel.

DMA capable controllers are everywhere, I don't think you'll find any storage controllers in your modern computer that don't do this.

Of course DMA only operates on byte ranges and not on files, but adding file system parsers to drives and disk controllers sounds like a way to introduce awful bugs and corruption. Assuming the OS keeps the necessary file system structures cached in RAM, plain old DMA should be good enough here.

There are even OS APIs for this - DirectStorage on Windows.

tchrist explains in that thread why neither uppercase nor lowercase is the best option:

> Mapping to lowercase doesn’t work for Unicode data, only for ASCII. You should be mapping to Unicode foldcase here, not lowercase. Otherwise yours is a Sisyphean task, since lowercase of Σίσυφος is σίσυφος, while lowercase of its uppercase, ΣΊΣΥΦΟΣ, is the correct σίσυφοσ, which is indeed the foldcase of all of those. Do you now understand why Unicode has a separate map? The casemappings are too complex for blindly mapping to anything not designed for that explicit purpose, and hence the presence of a 4th casemap in the Unicode casing tables: uppercase, titlecase, lowercase, foldcase.

of course 'σίσυφοσ' is not correct as a written word but if you were to encounter it then you should clearly consider it equivalent to 'σίσυφος'

If someone asks you a physics question about a car being dropped into the ocean, generally you don't have to worry about the make and model of the car.

If you know more than someone else, that's great - but in that case please share some of what you know, so the rest of us can learn. Just putting another person down doesn't help.

https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor...

How do you deal with these onerous constraints? Do you have a system for deciding how many copies of archive.org to keep locally?

It is sensible to consider the I/O speed of things other than spinning disks. Especially when they are exceptionally commonplace in consumer devices and developer workstations.

Your use case of people running desktop with 100TB is niche, for $100 you can get a very fast 1TB nvme drive now days, which is fine for 99.99% of the population.

On the other hand, ignoring my media collection, both my personal computer and server only need a few hundred GB of storage. SSDs are cheap enough that they are a no-brainer: they are physically a lot smaller, quieter, and more resilient. The orders-of-magnitude better IO speed doesn't hurt either, even if most of it is wasted on me.

1TB NVMe drives are now less than $75. I could get a 1TB HDD for $40 or a 3TB one for $75, but why bother?