[1]: https://github.com/sirupsen/napkin-math

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.)

In other words, when measured E2E in the context of a larger work-step (one large enough to be interrupted by a context-switch), the mean, amortized difference between the two types of fetch becomes <3x.

Top of my wishlist for future architectures is “more, lower-width memory channels” — i.e. increased intra-CPU NUMAification. Maybe something CXL.mem will roughly simulate — kind of a move from circuit-switched memory to packet-switched memory, as it were.

But it's not going to be easy - for a sense of scale I just tested a 7950x at stock speeds with stock JEDEC DDR5 timings. I inserted a bunch of numbers in an 8GB block of memory, and with a deterministic random seed randomly pick 4kb pages, computing their sum and eventually reporting that (to avoid overly clever dead-code analysis, and make sure the data is fully read).

With an SSD-friendly 4K page size that resulted in 2.8 million iops of QD1 random read. By comparison, a web search for intel's 5800x optane's QD1 results shows 0.11 million iops, and that's the fastest random read SSD there is at those queue depths, AFAIK.

If you add parallelism, then ddr5 reaches 11.6 million iops at QD16 (via 16 threads), fast SSDs reach around 1 million, the optane reaches 1.5 million. An Epyc Genoa server chip has 6 times as many DDR5 memory channels as this client system does; and I'm not sure how well that scales, but 60 million 4kb random read iops sounds reasonable, I assume. Intel's memory controllers are supposedly even better (at least for clients). Turning on XMP and PBO improves results by 15-20%; and even tighter secondary/tertiary timings are likely possible.

I don't think you're going to reach those numbers not even with 24 fast NVMe drives.

And then there's the fact that I picked the ssd-friendly 4kb size; 64-byte random reads reach 260 million iops - that's not quite as much bandwidth as @ 4kb, but the scaling is pretty decent. Good luck reaching those kind of numbers on SSDs, let alone the kind of numbers a 12-channel server might reach...

We're getting close enough that the loss in performance at highly parallel workloads is perhaps acceptable enough for some applications. But it's still going to be a serious engineering challenge to even get there, and you're only going to come close under ideal (for the NAND) circumstances - lower parallelism or smaller pages and it's pretty much hopeless to arrive at even the same order of magnitude.

If that scaled, it would be 9.6M IOPS from 24xNVMe.

Still, a mere factor 7 isn't a _huge_ difference. Plenty of use cases for that, especially since NAND has other advantages like cost/GB, capacity, and persistence.

But it's also not like this is going to replace dram very quickly. Iops is one thing, but latency is another, and there dram is still much faster; like close to 1000 times faster.

And you wouldn't see the speed improvement on RAID0 NVMe drives except extremely rare fully sequential operations lasting for at least tens of seconds.

You also can try it just by running a VM with iSCSI boot on your current desktop.

But I look at it this way. You need 40gbit networking for a single pci3 nvme ( and newer drives can saturate that, or close )

And because you're throttling throughput you'll see much more frequent, longer, queuing delays, on the back of a network stack that ( unless you're using rdma ) is already 5x-10x slower than nvme.

It'll be fast enough for lots of things, especially home/lab use, and it'll be amazing if you're upgrading from sata spinning disk.. but 10gbit is slow by modern storage standards.

Of course, that's not the only consideration. Shared storage and iscsi in particular can be extremely convenient! And sometimes offers storage functionality that clients don't have ( snapshots, compression, replication )

Don't have anything on the hands to look if the boot firmware even allows to set 9k, but I didn't touch iSCSI boot for a long time, so I would take your word for it.

> But I look at it this way. You need 40gbit networking ... is already 5x-10x slower than nvme.

This one.

> It'll be fast enough for lots of things, especially home/lab use

Yep, in OP's case I would consider just leaving the OS on the local [fast enough] drive and using iSCSI (if for some reason NFS/SMB doesn't fit) for any additional storage. It would be fast enough for almost everything, while completely eliminating any iSCSI boot shenanigans /me shudders in Broadcom flashbacks.

Another neat thing about iSCSI is what you can re/connect it to any device on the network in a couple of minutes (first time, even faster later), sometimes it comes really handy.

Ugh, ISCSI does have queueing so you can have many operations in flight, and one operation doesn't really translate to one packet in the first place, kernel will happily pack few smaller operations to TCP socket into one packet when there is load.

The single queue is the problem here but dumb admin trick is just to up more than one IP on the server and connect all of them via multipath

And here comes the latency! shining.jpg

It wouldn't be a problem for a desktop use of course[0], especially considering what 90% of operations are just read requests.

My example is crude and was more to highlight what iSCSI, by virtue of running over Ethernet, inherently has a limit of how many concurrent operations can go in one moment. It's not a problem for a HDD packed SAN (HDDs would impose an upper limit, because spinning rust is spinning) but for a NVMe (especially with a single target) it could diminish the benefits of such fast storage.

> The single queue is the problem here but dumb admin trick is just to up more than one IP on the server and connect all of them via multipath

Even on a single physical link? Could work if the load is queue bound...

[0] hell, even on 1Gb link you could run multiple VMs just fine, it's just when you start to move hundreds of GBs...

>And here comes the latency! shining.jpg

Not really, if you get data faster than you can send packets (link full) there wouldn't be that much extra latency from that (at most one packet length which at 10Gbit speeds is very short) and it would be more than offset by the savings

Then again I'd guess that's mostly academic as I'd imagine not very many ISCSI operations are small enough to matter. Most apps read more than a byte at a time after all, hell, you literally can't read less than a block from a block device which is at least 512 bytes.

>> The single queue is the problem here but dumb admin trick is just to up more than one IP on the server and connect all of them via multipath

> Even on a single physical link? Could work if the load is queue bound...

You can also use it to use multiple NICs without bonding/teaming, althought it is easier to have them in separate network, IIRC linux had some funny business when if you didn't configure it correctly for traffic in same network it would pick "first available" NIC to send it and it needed /proc setting to change

To elaborate, default setting for /proc/sys/net/ipv4/conf/interface/arp_ignore (and arp_announce) is 0 which means

> 0 - (default): reply for any local target IP address, configured on any interface

> 0 - (default) Use any local address, configured on any interface 1

IIRC to do what I said required

    net.ipv4.conf.all.arp_ignore=1
    net.ipv4.conf.all.arp_announce=2

It is, that mattered on 1Gbit links with multiple clients, ie any disk operations in VMs while there is vMotion running on the same links - you could see how everything started to crawl (and returned back after vMotion completed). For 10Gbit you need way, way more load for it to matter.

> You can also use it to use multiple NICs without bonding/teaming

You MUST (as in RFC) use multiple links without bonding and I learned to not to use LACP the hard way (yea, reading docs before is for pussies).

After second attempt I understood the implication (multiple NICs in the same IP network), but this is a self inflicted wound, usually. You don't even need a physically separate networks (VLANs), but using separate IP networks works fine, it's up to initiator to use RR/LB on them.

> it would pick "first available" NIC to send it

Yep, the usual magic of doing things to be easier for average folks. In the same vein - you need to disable Proxy ARP in any modern non-flat network or you will get shenanigans what would drive you mad.

iSCSI gotta eat some of your CPU (you're changing "send a request to disk controller and wait" to "do a bunch of work to create packet,send it over the network, and get it back) if you don't have card with offload, it also might kinda not be fast enough to get the most out of NVMe, especially more in RAID0

And, uh, just don't keep anything important there...

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.

I get ~30 GiB/s for threaded sequential memory reads, but ~4 GiB/s for SSD. However, I think the SSD number is single-threaded and not even with io_uring—so I need to regenerate those numbers. It's possible it could be 2-4x better.

[1]: https://github.com/sirupsen/napkin-math

But as I mentioned, there's caching upon caching, and also protocol level optimizations, and hardware-level considerations (physical block size may be quite large but is generally unknown).

It's nearly impossible to benchmark this stuff in a meaningful way. Or rather, it's nearly impossible to know what you are benchmarking, as there are a lot of nontrivially stateful parts all the way down that have real impact on your performance.

There are so many moving parts I think the only meaningful disk benchmarks consider whatever application you want to make go faster. Do the change. Is it faster? Great. Is it not? Well at least you learned.

Assuming that you run the experiments on NVMe SSD which is attached to PCIe 3.0, where theoretical maximum is around 1GB/s per each lane, I am not sure I understand how do you expect to go faster than 4 GiB/s? Isn't that already a theoretical maximum of what you can achieve?

And I'm pretty sure that parent comment doesn't own such a machine because otherwise I'd expect 7-8GB/s figure to be reported in the first place.

I’d guess that they’re a small minority of devices at the moment.

4.0 might not be common, but surprisingly it is now the previous generation!

I'm not sure how they calculated the theoretical limit of 42.4 GBPS, but they have multiple measurements higher than 30 GBPS.

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...

This applies to a single point query in a single tree.

The latency is reduced by overlap in obvious ways as soon as you have (1) a range query because it can read multiple subtrees in parallel, or (2) a query that reads multiple indexes in parallel, or (3) multiple queries from the application to the database in parallel.

This is why it's useful to design applications to make multiple queries in parallel. Web applications are a great example of this. Most applications where I/O performance matters at all have some natural way to parallelise queries.

Less obviously, the interior blocks of a B-tree are a relatively small part of a B-tree. I.e. most of the space is in used leaf blocks. If the database's cache strategy gives preference to interior nodes, and even more preference to nodes closer to the root of a tree, often several interior layers of the tree can fit entirely in RAM and the effect is is to reduce the latency of tree lookups further once the cache is warmed up.

Then even in large databases (a few TB), the latency of a single point query is reduced to a one or two read IOPS (because the leaf page to read which contains the query result is calculated from in-memory data). The application-visible query time is very similar to the I/O subsystem's timing characteristics, and a few MQPS are achievable (= "million queries per second"). Not many database engines achieve this, because they were designed in an area where I/O was much slower, but the I/O architecture does support it.

Source: Wrote a performance-optimised database engine for blockchain archive data, which is extremely random access (because of hashing), in the multiple terabytes range, and the application is bottlenecked on how many queries per second it can achieve. It's like the ideal case for working on random-access I/O performance :-)

For example a tree-index can be parallelized by walking down different branches. On top of that one can issue a prefetch for the next node (on each branch) while processing the current ones.

With spinning rust you have to wait for the sector you want to read to rotate underneath the read head. For a fast 10.000 RPM drive, a single rotation takes 6 milliseconds. This means that for random access the average latency is going to be 3 milliseconds - and even that's ignoring the need to move the read head between different tracks! Sequential data doesn't suffer from this, because it'll be passing underneath the read head in the exact order you want - you can even take the track switching time into account to make this even better.

SSDs have a different problem. Due to the way NAND is physically constructed it is only possible to read a single page at a time, and accessing a single page has a latency of a few nanoseconds. This immediately places a lower limit on the random read access time. However, SSDs allow you to send read commands which span many pages, allowing the SSD to reorder the reads in the most optimal way, and do multiple reads in parallel. This means that you only have to pay the random access penalty once - not to mention that you have to issue way fewer commands to the SSD.

SSDs try to make this somewhat better by having a very deep command queue: you can issue literally thousands of random reads at once, and the SSD will reorder them for faster execution. Unfortunately this doesn't gain you a lot if your random reads have dependencies, such as when traversing a tree structure, and you are still wasting a lot of effort reading entire pages when you only need a few bytes.

Curious to hear your thoughts on this thread if you have time to share: https://news.ycombinator.com/item?id=33752870

So, this mean Btrees suffer? Which could be the most optimal layout for a database storage where only SSD matters?

I'm working in one that is just WAL-only and scanning all in each operation (for now!) and wanna see what I can do for improve the situation.

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

To measure this I would have N processes reading the file from disk with the max number of parallel heads (typically 16 I think). These would go straight into memory. It's possible you could do this with one process and the kernel will split up the block read into 16 parallel reads as well, needs investigation.

Then I would use the rest of the compute for number crunching as fast as possible using as many available cores as possible: for this problem, I think that would basically boil down to a map reduce. Possibly a lock-free concurrent hashmap could be competitive.

Now, run these in parallel and measure the real time from start to finish of both. Also gets the total CPU time spent for reference.

I'm pretty sure the author's results are polluted: while they are processing data the kernel is caching the next block. Also, it's not really fair to compare single threaded disk IO to a single process: one of the reasons for IO being a bottleneck is that it has concurrency constraints. Never the less I would be interested in both the single threaded and concurrent results.

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.

Regarding OS caching: I'm trying to avoid this by clearing caches with the "sysctl vm.drop_caches=3" command. Note that I show both cached and uncached numbers.

Also I don't think it was clear you were running "sysctl vm.drop_caches=3" between benchmarking runs of your optimizations. Your table seemed to indicate those were generic initial read/write benchmarks from either dd or hardparm. The site you linked to also had comments on it stating dd is not very good for benchmarking, suggesting fio & a different site[1].

1. https://linuxreviews.org/HOWTO_Test_Disk_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.

An obvious optimization would be to utilize all available CPU cores by using the MapReduce pattern with multiple threads.

I believe that'd be necessary for a fair conclusion anyway, as you can't claim that I/O isn't the bottleneck, without utilizing all of the available CPU and memory resources.

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.

For large files you should get almost embarrassing parallelism.

Remember that fizzbuzz on HN that hit GB/s? Mostly SIMD. Zero multi-threaded IIRC.

If I/O wasn't the bottleneck, I guess you can parallelize reading, but what are you gaining?

If you're writing to files, most of the time the parallism will be hard to implement correctly. SQLite doesn't support parallel writes for example.

I think your SSD/network link/database might be able to work in parallel even when Python can't. Details:

Suppose I am scraping a website using a breadth-first approach. I have a long queue of pages to scrape. A single-threaded scraper looks like: pop the next page in the queue, block until the web server returns that page, repeat. A multi-threaded scraper looks like: thread wakes up, pops the next page in the queue, sleeps until the web server returns that page, repeat. With the multi-threaded scraper I can initiate additional downloads while the thread sleeps.

My assumption here is that the download over the network is at some level being performed by making a system call (how could it not be?) And once you have multiple system calls going, they can be as parallel as the OS permits them to be; the OS doesn't have to worry about the GIL. And also the server should be able to serve requests in parallel (assuming for the sake of argument that the server doesn't suffer from the GIL).

Same essential argument applies to the database. Suppose I'm communicating with the database using IPC. The database isn't written in Python and doesn't suffer from the GIL. Multiple Python threads can be sleeping on the database while the database processes their requests, possibly in parallel if the db supports that.

I think this argument could even work for the SSD if the kernel is able to batch your requests in a way that takes advantage of the hardware, according to this person: https://news.ycombinator.com/item?id=33752411

Very curious to hear your thoughts here. Essentially my argument is that the SSD/network link/database could be a "bottleneck" in terms of latency without being the bottleneck in terms of throughput (i.e. it has unused parallel capacity even though it's operating at maximum speed).

Of course it will. Near every serious DB will allow to work on multiple requests in parallel and unless the DB itself is on something that's slow you will get data faster from 2 parallel requests than from serializing them

NVMe SSDs in particular can easily fill what single thread can read, just run fio with single vs parallel threads to see that.

> If you're writing to files, most of the time the parallism will be hard to implement correctly. SQLite doesn't support parallel writes for example.

That's just one random example. If all you do is "read data, parse ,write data" in some batch job you can have massive parallelism. Sharding is also easy way to fill up the IO.

https://www.sqlite.org/cgi/src/doc/begin-concurrent/doc/begi...

In Python yes. I missed that. The Go implementation would still benefit from multiple threads, wouldn't it?

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.

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

You could say the same about the existing implementation as that reads the whole file into memory instead of processing it in chunks.

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).

We pay 7k per month for RDS that can do barely 2k iops.. in the same time a machine at hetzner does 2 million iops for 250 euro per month (not to mention it also have 4x more codes and 5x more ram).

So, even though I/O is no longer the bottle neck physically, it still is a considerable issue and design challenge on the cloud.

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... ;)

Over last ~6 years we did "is it worth going to cloud" calculation few times and it was always ridiculously more expensive.

PostgreSQL is pretty much parallel but i know what you mean...the beehive ;)

Could you please explain where this number comes from?

>Yeah, that's a myth now. It's not current advice.

It's not and you know it, keep it under 72% believe me if you want a performant zfs (especially if you delete files and have many snapshots...check the YT linked at the end)

>>Keep pool space under 80% utilization to maintain pool performance. Currently, pool performance can degrade when a pool is very full and file systems are updated frequently, such as on a busy mail server. Full pools might cause a performance penalty, but no other issues. If the primary workload is immutable files (write once, never remove), then you can keep a pool in the 95-96% utilization range. Keep in mind that even with mostly static content in the 95-96% range, write, read, and resilvering performance might suffer.

https://web.archive.org/web/20150905142644/http://www.solari...

And under no circumstances go over 90%:

https://openzfs.github.io/openzfs-docs/Performance%20and%20T...

>An introduction to the implementation of ZFS - Kirk McKusick

https://www.youtube.com/watch?v=TQe-nnJPNF8

>ASCII: it’s okay to only support ASCII

>Threading: it should run in a single thread on a single machine

>Stdlib: only use the language’s standard library functions.

This is truly 1978 all over again. No flame graphs, no hardware counters, no bottleneck analysis. Using these 'optimizations' for job interviews is questionable at best.

[1] https://benhoyt.com/writings/count-words/

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.

I come from gamedev low level coding and performance analysis so I understand that my point of view is not normal xD

I've seen comments about Google multiple times here where people say you wont be getting promotions unless you're shipping new things -- maintaining the old wont do it.

But if you get to something core enough, it seems like the numbers would be pretty tangible and easy to point to during perf review time?

"Found a smoother way to sort numbers that reduced the "whirrrrrr" noise our disks made. It turns out this reduces disk failure rates by 1%, arrested nanoscale structural damage to the buildings our servers are in, allowed a reduction in necessary PPE, elongaded depreciation offsets and other things -- this one line of code has saved Google a billion dollars. That's why my compensation should be increased to include allowing me to fall limply into the arms of another and be carried, drooling, into the office, where others will dress me"

In this hypothetical scenario, would a Googler be told "Your request has been approved, it may take one or two payment periods before your new benefits break into your apartment" or "No, you need to ship another chat program before you're eligible for that."?

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/

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.

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."

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...

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.

But that intuition was completely wrong. The 100K CSV files only add up to about 2GB. Despite being many small files reading through them all is pretty fast the first time, even on Windows, and then they're in the cache and you can ripgrep through them all almost instantaneously. The pretty fast parser library is fast because it uses runtime code generation for the specific object type that is being deserialized. The overhead of allocating a bunch of complex parser and typeconverter objects, doing reflection on the parsed types, and generating code for a parser, means that for parsing lots of tiny files its really slow.

I had to stop worrying about it because 2 minutes is fast enough for a batch import process but it bothers me still.

Edit: CsvHelper doesn't have APIs to reuse parser objects. I tested patching in a ConcurrentDictionary to cache the generated code and it massively sped up the import. But again it was fast enough and I couldn't let myself get nerd sniped.

Edit2: the import process would run in production on a server with low average load, 256GB RAM, and ZFS with zstd compression. So the CSV files will live permanently in the page cache and ZFS ARC. The import will probably run a few dozen times a day to catch changes. IO is really not going to be the problem. In fact, it would probably speed things up to switch to synchronous reads and remove all the async overhead. Oh well.

[0]: https://www.joelverhagen.com/blog/2020/12/fastest-net-csv-pa...

The latency of reading from disk is indeed very slow compared to CPU instructions.

A 3ghz clock speed processor is running 3 billion (3,000,000,000 cycles a second) and some instructions take 1 cycle. You get 3 cycles per nanosecond. A SSD or spinning disk access costs many multiples of cycles.

Read 1 MB sequentially from SSD* 1,000,000

That's a lot of time that could be spent doing additions or looping.

https://gist.github.com/jboner/2841832

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

The parsing challenge is complex enough that it will always be faster to extract the data from the network than it is to process it. As a result excess data must be stored until it can be evaluated or else it must be dropped, therefore the primary processing limitation is memory access not CPU speed executing instructions. JavaScript is a garbage collected language, so you are at the mercy of the language and it doesn't really matter how you write the code because if the message input frequency is high enough and large enough memory will always be the bottleneck, not the network or the application code.

In terms of numbers this is provable. When testing WebSocket performance on my old desktop with DDR3 memory I was sending messages (without a queue or any kind of safety consideration) at about 180,000 messages per second. In my laptop with DDR4 memory the same test indicated a message send speed at about 420,000 messages per second. The CPU in the old desktop is faster and more powerful than the CPU in the laptop.

CPU and RAM are pretty fast. I do a live-coding interview question and I ask people do to a naive implementation first, then later I ask about possible optimizations. A third to a half of candidates want to do fewer RAM accesses and oh by is that the wrong avenue for this problem - especially when they just wrote their solution in Python and you could get a 10x-20x speedup by rewrite in C/C++/Go/Rust/etc.

Network is IO too. Network is pretty fast, datacenter-to-datacenter, but end users can still have their experience improved with better encoding and protocol; and outbound bandwidth bills can be improved by that too.

The default malloc in glibc does not pad the values given to sbrk, so you have to do a syscall for every 4k chunk of memory (the pagesize). So unless you do lots of very small (<<4k) allocations, you call sbrk pretty often.

You will also page fault when you access the new pages, and this traps into kernel code again.

So yeah, you are technically correct that some allocations may be fast because the memory is already available and mapped. Allocations, on average, are still slow because it involves context switches to the kernel (potentially multiple).

TLDR: you make it sound like a syscall within malloc is rare, but many/most allocations will trigger a syscall.

Furthermore, memory which is freed is often not returned to the os, either for fragmentation (you've used sbrk..) , or performance reasons (minimize syscalls), and put in a free list instead. The next call to malloc then will not require a syscall, if it can be satisfied with existing freed blocks.

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.

Sequentially reading a file on a spinny laptop disk was about 80-100 MB/s. On an SSD that went up to 400-500 MB/s for me.

That's the sequential case! What about random access? I tried an experiment where I memory mapped a large file and started updating bytes at random. I could get the rate down to kilobytes/sec.

Even though we've all heard that SSDs don't pay as much as a penalty for random access as spinny disks, it's still a huge penalty. Sequential spinny disk access is faster than SSD random access.

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.

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.

> In the memory-mapped case, that means using multiple threads.

My gut tells me I'd lose more to contention/false-sharing than I'd gain through multithreading - but I haven't done the experiment.

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.

Cool, lots of IOPS!

But like I said, I got it down to kilobytes/sec.

This [0] comment is totally on point.

Also note what a consumer SSDs can be made even with a single flash chip. A more performant ones are made of bunch of chips internally (essentially a RAID0 with some magic) so they can do a parallel operations if the data resides on the different flash blocks. Still, if your thread is only doing one operation a time with blocks < flash rewrite block size you will hit the write amplification anyway.

I think if you do the same test but without a memory mapped file (ie let the OS and disk subsystem do their thing) you will get much more speed.

[0] https://news.ycombinator.com/item?id=33751973

It’s a throughput number, not a single operation, completion, followed by the next one.

however, a spinning disk doing a sequential access is not doing 25600 iops

if the sequential access lasts 10 seconds it is doing 0.1 iops

  time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | sort --buffer-size=50M | uniq -c | sort -hr > /dev/null

I'm quite puzzled why `sort is so much slower, especially as it does sorting in parallel utilizing multiple CPU cores, while the Python implementation is single-threaded.

Does somebody have an explanation for that?

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 when I also get:

# 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 0m23.174s user 0m23.309s sys 0m1.234s

So my result is 10x slower than yours.

What are you running this on and where do I get one?

  2.3 GHz Intel Core i5
  8 GB 1333 MHz DDR3
  Intel HD Graphics 3000 512 MB
  macOS High Sierra 10.13.6 (17G14042)
  512 GB PLEXTOR PX-512M5Pro SSD (Get Info says I installed it July 2, 2011 but it might be a clone of another drive)

I really like it, but will probably have to sell it because it has various software failures, like sometimes one of my displays won't turn on or goes black and I have to restart. That bug seems to be fixed on newer macOSs like the one on an Intel MacBook Pro I use for work, but Apple artificially sunsets their hardware by preventing newer versions of macOS from being installed and not back-porting bug fixes to previous macOSs. Since pretty much all computers today are Turing-complete, that feels.. disingenuous.

Computers haven't gotten appreciably faster for roughly 15 years since R&D funding shifted to mobile in 2007 and Moore's Law ended. All that matters today is whether we are using an SSD and how wide the memory bus is, since speed there hasn't changed much either, just latency. And Apple's not the only one treading water. PCs often suffer from mismatched hardware, so maybe an Intel i9 gets installed on a logic board with a memory bus too slow to recruit it. I built a gaming PC a few years back and I may have inadvertently underpowered it by putting most of the budget into the RTX 2070. Since video cards can't do the everyday workloads we're discussing, I mostly consider them a waste of time and mourn what might have been had CPUs kept improving instead.

Apple's Arm M1 is a logical progression off of Intel, but I can't really endorse it, since they chose a relatively complex architecture where a big dumb array of cores would have been more scalable. If some indie brand comes along and builds one of the 1000+ core CPUs I've blabbered on about, I can't say that I'll have much sympathy for the current big players.

Due to all of that, I perceived computers in 2010 as being roughly 1000 times slower than they could/should be had they kept up with Moore's Law, and computers in 2020 as being roughly 1000000 times slower (the ratio of GPU to CPU FLOPs for example). It doesn't help that stuff like Spotlight and Safari eagerly take 100+% CPU or that basically all PCs are bogged down with either spyware or the daemons that supposedly find and remove spyware (thank you M$). Or that we don't have the network computing that Sparc had in the 1990s, where all of the computers on the LAN were available for additional cores seamlessly. Just slow on top of slow on top of slow under surveillance capitalism yay!

</rant>

https://github.com/koraa/huniq

* Splitting long lines is slow[1]

* Can Parallel::ForkManager speed up a seemingly IO bound task?[2]

In both cases, Perl is the language used (with a little C thrown in for [1]), but they are in a similar vein to the topic of this post. In [1], I show that the slowness in processing large files line by line is not due to I/O, but due to the amount of work done by code. In [2], a seemingly I/O bound task is sped up by throwing more CPU at it.

[1]: https://www.nu42.com/2013/02/splitting-long-lines-is-slow.ht...

[2]: https://www.nu42.com/2012/04/can-parallelforkmanager-speed-u...

Pick a small enough bound and an O(n^2) algorithm behaves better than an O(n log n). This is why insertion sort is used for sorting lengths less than ~64, for example.

Big O notation doesn't take into account constant factors of overhead or plain old once-per-run overhead.

The real problem to me is that languages are too high-level and hiding temporary allocations too much. If you had to write this in C, you would naturally avoid unnecessary allocations, cause alloc / free in the hot loop looks bad.

Presumably soon enough it's very unlikely you find any new word (actually it's 10 passes over the same text) and most keys exist in the hashmap, so it would be doing a lookup and incrementing a counter, which should not require allocations.

Edit: OK, I've ran OP's optimize C-version [1] and indeed, it only hits 270MB/s. So, OP's point remains valid. Perf tells me that 23% of all cache refs are misses, so I wonder if it can be optimized to group counters of common words together.

[1] https://benhoyt.com/writings/count-words/

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.

It’s certainly more performant than any dynamically typed scripting language: JavaScript, Python, Ruby, etc but it’s probably closer to C#.

whether i/o is the bottleneck depends on what you're doing and on which computer, and that's been true for at least 50 years

"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.

That's what compilers are for. I tried to improve the C version to make it friendlier to the compiler. Clang does a decent job:

https://godbolt.org/z/o35edavPn

I'm getting 1.325s (321MB/s) instead of 1.506s (282MB/s) on a 100 concatenated bibles. That's still not a 10x improvement though; the problem is cache locality in the hash map.

A better way to "scale up" is to concatenate various other things from Project Gutenberg: https://www.gutenberg.org/ At least then you have "organic" statistics on the hash.

C# offers that out of the box, and the solution is much simpler there.

Pass StringComparer.OrdinalIgnoreCase or similar (InvariantCultureIgnoreCase, CurrentCultureIgnoreCase) to the constructor of the hash map, and the hash map will become case-agnostic. No need to transform strings.

Though the values should mostly be quite short, so a vectorised comparison might not even trigger as it wouldn't have the time to "stride": only one word of the top 10 even exceeds 4 letters ("shall", a hair under a million in my corpus).

Here’s implementation of the hash function used by that StringComparer.OrdinalIgnoreCase: https://source.dot.net/#System.Private.CoreLib/src/libraries... As you see, it has a fast path for ASCII-only input strings.

Which doesn't matter because I'm talking about identical strings, so they will hash the same by definition, and they will have to be compared.

So the question is how fast the CI hash and equality operate compared to the CS ones.

And I asked about comparison because I assumed that would be the costlier of the two operations, relative to its CS brethren.

If the string is ASCII like in the OP’s use case, I think the difference is not huge.

CS comparison looks more optimized, they have an inner loop which compares 12 bytes as 3 64-bit values: https://source.dot.net/#System.Private.CoreLib/src/libraries...

CI comparer doesn’t do that, it loads individual UTF-16 elements: https://source.dot.net/#System.Private.CoreLib/src/libraries... But still, it’s very simple code which does sequential memory access.

> And I asked about comparison because I assumed that would be the costlier of the two operations, relative to its CS brethren.

I think the bottleneck is random memory loads from the hash table.

Hashing and comparison do sequential RAM access. The prefetcher in the CPU will do its job, you’ll get 2 memory loads every cycle, for short strings going to be extremely fast. If that hashtable doesn’t fit in L3 cache, the main memory latency is much slower than comparing strings of 10-20 characters, no matter case sensitive or not.

But I’m sure it gonna be much harder.

For non-ASCII strings, converting case may change their length in bytes. You don’t even know in advance how much memory you need to transform 2GB of input text (or 1MB buffer if streaming). And if streaming, you need to be careful to keep code points together: with a naïve approach you gonna crash with a runtime exception when you split a single codepoint between chunks.

English words are 99.9% ASCII, but that remaining 0.1% like “naïve” is not. The C# standard library is doing the right thing for this use case. Specifically, for 99.9% of words the CI comparer will use the faster ASCII-only code to compare or hash, and only do the expensive shenanigans for small count of non-ASCII words.

Note how C# makes the implementation much simpler. A single parameter passed to the constructor of the Dictionary<string,Something> makes it implement case-insensitivity automagically.

No, but at least you have direct access to the intrinsics in C. To get vectorization in Go, you have to implement it in C and link that into your Go program.

Go has an assembler which does not require implementing anything in C (though the assembler uses a more C-style syntax), nor critically does it require using CGo linkage. It's used to implement many hot paths in the stdlib.

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.

if all your scans had to reread the file from nvme it would take five times as long if we extrapolate from those figures

not 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.

This is not true. I thought the same thing and you are right in regards to base line clock speed. But the performance is still increasing. I just got a new PC at work with a 2021 high-end CPU and it has 200% single core performance of the 2015 mid-range CPU in my private PC:

https://www.cpubenchmark.net/compare/4597vs2599/Intel-i9-129...

Also, the comment you're quoting is talking about clock speed, and the link you provided literally shows the same base clock speed - 3.2 GHz. Intel progressively pushed turbo speed higher, but that the speed you could have achieved yourself by overclocking.

On my water cooled and specifically tweaked desktop- yes. It’ll hold max boost indefinitely, even with all threads. (getting to about 80c after 10 mins). Single-thread max is faster, and it’ll hold that as well.

My laptop will pull power within 15 seconds and be down to base clocks in a couple mins. Unless I set it down outside and it’s very cold.

Other things changed. The turbo clockspeed is one of them.

Technically we have gone from 3.3gz- 3.9gz base frequency, 4.1-4.2 single core boosts, 4.7ghz heavy OC in Haswell to

4.3 and 3.0 base clock for efficiency/perf cores, with boosts to 5.4 ish, stable 5.8ghz all core frequency with heavy OC, and even pushing 6.something GHz single core with a good setup.

But then again, this is on the more extreme ends. Mainstream laptops have remained relatively stable.

re Python MP:

On my 12700k, I saw almost linear scaling (per core, not thread) with multiprocessing when loading stuff from the disk for ML applications and processing. This was with the datasets library.

(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.

PhotoStructure is a non-trivial app written in TypeScript for both frontend and backend tasks.

Coming from Scala, I initially used a lot of Array.map, Array.foreach, and, to handle things like Some/None/Either:

function map<T,U>( maybe: <T|undefined>, f: (t:T) => U )

According to the V8 memory inspector, all those tiny fat-arrow functions can hammer the GC (presumably due to stack allocations and pulling in local context). Replacing large array iteration with for loops was a big win.

Also, handling large files with a streaming parser when possible, instead of reading them entirely into memory, another win.

Buffer concatenation may be faster by pushing read chunks onto an array, and joining the lot at the end, rather than incrementally appending with .concat.

When memoizing functions, if they themselves return functions, watch out for fat-arrows if you didn't need the caller's context (which may prevent gc from unexpectedly retained variables).

But the first step should always be to profile your app. You can't assert improvement without a baseline.

> If you’re processing “big data”, disk I/O probably isn’t the bottleneck.

If it fits on a single machine, it is by definition not big data. When you're dealing with really big data, it's likely coming from another machine, or more likely a cluster of them. Networks can also be pretty fast, but there will still be some delay associated with that plus the I/O (which might well be on spinning rust instead of flash) on the other end. Big data requires parallelism to cover those latencies. Requires. It might be true that I/O is no longer likely to be the bottleneck for a single-threaded program, but leave "big data" out of it because in that world I/O really is still a - if not the - major limiter.

For Python optimisation, have you tried PyPy? I ran my same code (zero changes) using PyPy, and I got 3.5x better speed.

I published my findings here [1].

[0] - https://github.com/avinassh/fast-sqlite3-inserts

[1] - https://avi.im/blag/2021/fast-sqlite-inserts/

Yes, I believe so as well. They have done many CPU optimisations, so it is likely to be faster

You also note that reading a file sequentially from disk is very fast, which it is, but there is no guarantee that the file's contents are actually sequential on disk (fragmentation), right? We'd have to see how the file was written, and I guess at worst you'd be reading sequential chunks of a hand-wavy 4KB or something depending on the file system and what not. I'm sure others can fill in the details.

Just nit-picking here.

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).

FWIW, all my recent performance wins have either been by reducing RAM I/O or restructuring work to reduce contention in the memory controller, even at the cost of adding significantly more work to the CPU.

Tons of files and random writes can bring even an enterprise flash ssd to its knees but Optane keeps on trucking

Running some search on a file on your 486-with-8-megs-of-RAM running Linux, where the file was in the operating system's cache, was dependent on the performance of the program, and the overhead of reading data from the cache through syscalls.

You can't handwave away the performance of the program with the argument that it will hide behind I/O even if that is true for cache-cold run because cache-hot performance is important. People run multiple different kinds of processing passes on the same data.

- Read file in one thread pool, streaming the chunks to...

- ...another thread pool, tokenise, count, sort the chunks and send them to ...

- ... merge in another thread pool. (basically map-reduce).

- please stop malloc'ing for each token

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

- SIMD would optimise your inner-loop quite a lot. However, there are optimised libraries for this, so you don't have to write this yourself.

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

Why is there no profiling? Why don't you check how the compiler interpreted your code and benchmark the subparts?

In addition, there are at least some errors in your optimised program:

- you can't lower-case by substract like you do. Non-ascii characters would fail.

- also you can't tokenising by comparing with c <= ' '. There are many characters which would break a string. See this exercise: https://campus.datacamp.com/courses/introduction-to-natural-...

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.

You could use one big buffer for all your words. Arguably that's bump allocation but it's much simpler than malloc.

The real alloc win would likely be some kind of small-string optimization, which Go (specifically, the requirements of its precise GC) makes difficult. This is probably my biggest performance frustration with Go, 16 bytes for a string and especially 24 for a slice is so much waste when often 99% of your data is smaller than that.

Continuing with standard python (pydata) and ok hw:

- 1 cheap ssd: 1-2 GB/s

- 8 core (3 GHz) x 8 SIMD: 1-3 TFLOPS?

- 1 pci card: 10+ GB/s

- 1 cheapo GPU: 1-3 TFLOPS?

($$$: cross-fancy-multi-GPU bandwidth: 1 TB/s)

For streaming like word count, the Floating point operation (proxy for actual ops) to Read ratio is unclear, and the above supports 1000:1 . Where the author is reaching the roofline on either is a fun detour, so I'll switch to what I'd expect of pydata python.

It's fun to do something like run regexes on logs use cudf one liners (GPU port of pandas) and figure out the bottleneck. 1 GB/s sounds low, I'd expect the compute to be more like 20GB+/s for in-memory, so they'd need to chain 10+ SSD achieve that, and good chance the PCI card would still be fine. At 2-5x more compute, the PCI card would probably become a new bottleneck.

> As you can see, the disk I/O in the simple Go version takes only 14% of the running time. In the optimized version, we’ve sped up both reading and processing, and the disk I/O takes only 7% of the total.

1. If I/O wasn't a bottleneck, shouldn't we optimize only reading to have comparable benchmarks?

2. Imagine program was running 100 sec, (14% I/O) so 14 seconds are spent on I/O. Now we optimize processing and total time became 70 seconds, if I/O wasn't a bottleneck, and we haven't optimized I/O, total disk I/O should become 20% of total execution time, not 7%.

Disk I/O:

> Go simple (0.499), Go optimized (0.154)

clearly, I/O access was optimized 3x and total execution was optimized 1.6x times. This is not a good way of measurement to say I/O is not a bottleneck.

I agree though things are getting faster.

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.

4-lane PCIe, as most nvme drives are. I havent seen drives with wider lanes though...

Enterprise SSDs only really have significantly higher endurance if you're looking at the top market segments where a drive is configured with much more spare area than consumer drives (ie. where a 1TiB drive has 800GB usable capacity rather than 960GB or 1000GB). Most of the discrepancy in write endurance ratings between mainstream consumer and mainstream enterprise drives comes from their respective write endurance ratings being calculated according to different criteria, and from consumer SSDs being given low-ball endurance ratings so that they don't cannibalize sales of enterprise drives.

Your poor Ceph performance with Samsung consumer SATA SSDs wasn't due to the NAND, but to the lack of power loss protection on the consumer SSDs leading to poor sync write performance.

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.

Of course I/O is the slowest, but it is fast enough to let most of the programmers not able to fully utilize it.

I don't see how that changes anything. There's a reason we use Big O rather than other notations. Their answer would still be correct.

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