21 ms·

I/O is no longer the bottleneck

• osigurdson 4y ago
  Compared to L1 cache reference, it certainly still is.
• Un1corn 4y ago
  Does someone have a comparison between common server ssds and consumer ssds? I wonder if the speed is equal or not
  • PaulKeeble 4y ago
    Hard drives are still about 150MB/s. 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.
    • js4ever 4y ago
      For me main difference between hdd and nvme is not really the throughput but the acces time. When you manipulate small files it's a lot more important
    • Dalewyn 4y ago
      It should be noted that those SSD speeds are all protocol limits rather than NAND flash limits. ~7GB/s is literally the maximum speed PCIE4 can provide, likewise ~3.5GB/s for PCIE3 and ~500MB/s for SATA3.
      • omgtehlion 4y ago
        > the maximum speed PCIE4 4-lane PCIe, as most nvme drives are. I havent seen drives with wider lanes though...
        • Dalewyn 4y ago
          Ah, right. Lanes. I should have mentioned those as well, thanks for catching that.
    • bluedino 4y ago
      Todays large hard drives are over 250MBs in sequential operations
  • sekh60 4y ago
    Consumer SSDs are trash for sustained writes since they get their top speeds from cache and use slower NAND. Enterprise SSDs tend to have better write endurance, and faster NAND. I have a small Ceph cluster and as an example when I first bought SSDs for it I tried consumer Samsung 870 Evo's. They performed worse than spinning rust.
    • wtallis 4y ago
      Consumer SSDs don't really use slower NAND; the QLC vs TLC ratio might be higher for the consumer SSD market than the enterprise SSD market, but a consumer TLC drive is using the same speed of NAND as an enterprise TLC drive (and likewise for QLC drives). 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.
    • menaerus 4y ago
      If that had been true what you say then we wouldn't be able to saturate the PCIe 3.0 x4 bus with consumer NVMe SSD which we absolutely can. The biggest difference is in the durability as mentioned in the comment below.
  • wtallis 4y ago
    Read speeds are similar between consumer and enterprise SSDs; they use the same flash and there's overlap with high-end consumer SSDs using the same controllers as entry-level and mid-range enterprise SSDs. 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.
• nimish 4y ago
  If you ignore latency sure. Optane is still the fastest storage by quite a bit. Flash has yet to catch up and might never do so. Tons of files and random writes can bring even an enterprise flash ssd to its knees but Optane keeps on trucking
• namkt 4y ago
  I would have thought that allocations in managed languages like Go/Python would have been the "fast" part of the processing. Isn't technically the GC that's slowing you down, and not the allocation per se? For one-shot input/output programs like these I guess you could tune the GC to kick in with less frequency. 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.
  • PaulKeeble 4y ago
    Files aren't stored sequentially in an SSD anyway, they are scattered all over the place physically on different blocks just due to the way SSDs work. This doesn't hurt their sequential read performance at all since they have no seek time they already have a lookup table from the physical block the OS sees to a virtual location within themselves. 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.
  • wtallis 4y ago
    > 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? 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.png 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).
• MrLeap 4y ago
  Interesting! This made me wonder -- would this kind of optimization be recognized and rewarded in colossal scale organizations? 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."?
  • PaulKeeble 4y ago
    They likely have become one of the 10k getting fired for "underperforming". Company management in basically all businesses don't like know it alls that do the opposite of what they are told regardless of the outcome.
    • plonk 4y ago
      Google's core services wouldn't work so reliably if they didn't value optimization and engineering. I don't work there, but I'm pretty sure that the SREs and the developers behind Search and Maps don't get fired based on how many products they launched.
    • vitiral 4y ago
      Is there a valid source for this number? All the articles I see seem to quote each other.
    • kevinventullo 4y ago
      You don’t know what you’re talking about.
• visarga 4y ago
  Loading 1GB json files is still slow.
  • mrkeen 4y ago
    If you specify the type of the data, not just the size, then yep: it wasn't really about the number of bytes read, but what the CPU had to do to process it.
  • flohofwoe 4y ago
    That's usually not because of IO but because of dumb memory management in the JSON parser implementation. Some JSON parsers build a huge tree out of individually allocated items for each JSON property, or in higher level languages, build an object/property tree out of the JSON structure. That's guaranteed to be slow for large trees.
  • krapp 4y ago
    I don't want to be that guy but having 1GB json files to begin with seems like the bigger problem.
  • omgtehlion 4y ago
    Not if you use SAX-like (or "evented") parser
• mrkeen 4y ago
  A few ballpark numbers I encountered: 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.
  • GrayShade 4y ago
    > Sequential spinny disk access is faster than SSD random access. 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.
    • mrkeen 4y ago
      I didn't think there'd be that much discussion on my point (seq hdd > rand sdd). > 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.
  • koolba 4y ago
    > Sequential spinny disk access is faster than SSD random access. 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.
    • deleted 4y ago
      [deleted]
    • kragen 4y ago
      it is true that spinning rust is slower than most ssds including nvme ssds even in sequential mode 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
• samsquire 4y ago
  My immediate thought was are you measuring throughput or latency? 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 https://gist.github.com/jboner/2841832
  • cb321 4y ago
    I agree - "IO bandwidth is no longer a BW bottleneck" would be a better title.
  • formerly_proven 4y ago
    And you get 2-4 instructions per cycle on average.
  • noctune 4y ago
    That is true, but assuming file I/O is blocking you also have to pay for a context switch to take advantage of that. But I guess you could avoid that using eg. io_uring.
• mrich 4y ago
  I have a hunch when rewriting the program in C/C++ or Rust this will change significantly.
  • jhfdbkofdchk 4y ago
    Writing this in Perl will have significantly different results. Can’t speak for Go but text processing in Python is slow.
  • civopsec 4y ago
    Not necessarily considering that he wrote that the Go version tries to avoid memory allocations.
• throwaway71271 4y ago
  EBS costs crazy crazy amounts for reasonable iops 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.
  • nix23 4y ago
    Well yes it's a total ripoff 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... ;)
    • samb1729 4y ago
      > remember never fill a zpool over 72% Could you please explain where this number comes from?
      • ewwhite 4y ago
        Yeah, that's a myth now. It's not current advice.
        • nix23 4y ago
          72% is my rule of thumb for write heavy production stuff (my absolute limit would be 75%) but it depends on record-size, raidz-level, if you have mostly write or mostly read workloads, how big your files are, how many snapshots you have, if you have a dedicated ZIL-Device and much more. For a Home-NAS (Movies etc) you can easy go up to 85%...if it's a "~WORM" workload maybe 90%...but resilvering can then be a thing of days (weeks?), depends on the raidz-level or mirror etc. >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.solarisinternals.com/wiki/index.php/ZFS_Best_Practices_Guide#General_Storage_Pool_Performance_Considerations https://web.archive.org/web/20150905142644/http://www.solari... And under no circumstances go over 90%: https://openzfs.github.io/openzfs-docs/Performance%20and%20Tuning/Workload%20Tuning.html#free-space 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 https://www.youtube.com/watch?v=TQe-nnJPNF8
• chewbacha 4y ago
  Wouldn’t memory allocation still be IO of a different resource? We’re still getting slowed down reading and writing bits to a storage device. Perhaps it’s not the hard drive but the claimed blocker here doesn’t appear to be CPU.
  • cb321 4y ago
    Indeed - for that particular problem a big cost is the "IO" from main memory "into the CPU cache". Ben is careful to qualify it as "disk" IO, but even this is somewhat vague. (as is "CPU cache" vs L3/L2/L1 - Ben's interview problem is highly L2 sensitive, I think, and increasing variety in that size will make results harder to interpret.) 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.
  • School-Cotton 4y ago
    Reading and writing to main memory is not usually called “IO” in this context.
  • dahfizz 4y ago
    Not really, no. Allocation involves reading/writing to memory, but that's not why it's slow. It's slow because allocation involves a context switch into the kernel. And an allocation algorithm itself isn't trivial.
    • zabzonk 4y ago
      user space code will not use the kernel and there will be no context switch. it will call a function such as malloc, which is a user-space function. malloc will then go on to interact with the memory allocation sub-system, which may occasionally need to ask the os for more memory via a system call, if the allocator is any good.
• austin-cheney 4y ago
  I encountered this myself yesterday when attempting to performance test WebSockets in JavaScript: https://github.com/prettydiff/share-file-systems/blob/master/documentation/websockets.md#challenges https://github.com/prettydiff/share-file-systems/blob/master... 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.
• Dunedan 4y ago
  > I haven’t shown an optimized Python version because it’s hard to optimize Python much further! (I got the time down from 8.4 to 7.5 seconds). It’s as fast as it is because the core operations are happening in C code – that’s why it so often doesn’t matter that “Python is slow”. 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.
  • deleted 4y ago
    [deleted]
  • plonk 4y ago
    > An obvious optimization would be to utilize all available CPU cores by using the MapReduce pattern with multiple threads. 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.
    • Waterluvian 4y ago
      You can use Processpool but at that point you’re way into re-architecting.
      • plonk 4y ago
        Not much more than the switch to MapReduce and threads. Actually the interface is exactly the same if you use executors from concurrent.futures.
      • znpy 4y ago
        inter-process communication has its own overhead though.
• buybackoff 4y ago
  Having dealt with several data parsers I would like to somehow estimate how much electricity is burned globally just for lazy implementations. E.g. in .NET non-devirtualized `Stream.ReadByte` is often one of the hottest methods in a profiler. It and related methods could easily be responsible for double-digit share of CPU when processing data. I mean, it's not IO but just pure overheads that disappear with custom buffering where reading a single byte is as cheap as it should be.
• stabbles 4y ago
  The title I/O is _no longer_ the bottleneck seems to suggest disk speed has caught up, while in reality the slowness is due to poor implementation (slow Python or Go with lots of allocations). 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/ https://benhoyt.com/writings/count-words/
  • davedx 4y ago
    Yeah I’ve worked on non trivial javascript codebases where allocations and gc mattered.
    • christophilus 4y ago
      I’d like to hear more about this.
      • mceachen 4y ago
        Not your OP, but I've got stories! 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.
• furstenheim 4y ago
  It would be nice to see this benchmark in Node.js with streams
• mastazi 4y ago
  Networking is I/O: API calls, database access, etc. - it's not just disk access. The article is deriving a generalised statement based on a very specific use case.
• Sirupsen 4y ago
  Yes, sequential I/O bandwidth is closing the gap to memory. [1] The I/O pattern to watch out for, and the biggest reason why e.g. databases do careful caching to memory, is that _random_ I/O is still dreadfully slow. I/O bandwidth is brilliant, but latency is still disappointing compared to memory. Not to mention, in typical Cloud workloads, IOPS are far more expensive than memory. [1]: https://github.com/sirupsen/napkin-math https://github.com/sirupsen/napkin-math
  • marginalia_nu 4y ago
    Depending on how your madvise is set up, it's often the case that sequential disk reads are memory reads. You're typically only paying the price for touching the first page in a sequential run, that or subsequent page faults come at a big discount. 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.
    • Sirupsen 4y ago
      `madvise(2)` doesn't matter _that_ much in my experience with [1] on modern Linux kernels. SSD just can't read _quite_ as quickly as memory in my testing. Sure, SSD will be able to re-read a lot into ram, analogous to how memory reading will be able to rapidly prefetch into L1. 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 https://github.com/sirupsen/napkin-math
      • marginalia_nu 4y ago
        I think the effects of madvise primarily crop up in extremely I/O-saturated scenarios, which are rare. Reads primarily incur latency, with a good SSD it's hard to actually run into IOPS limitations and you're not likely to run out of RAM for caching either in this scenario. MADV_RANDOM is usually a pessimization, MADV_SEQUENTIAL may help if you are truly reading sequentially, but may also worsen performance as pages don't linger as long. 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.
• williamcotton 4y ago
  Wouldn’t it be nice if we could specify the allocators in GC languages? Like, why not expose a bump allocator arena to Python with a manual release?
  • krapp 4y ago
    I don't know if C++ counts as a "GC language" per se, but you can write custom allocators for STL containers (eg here: https://betterprogramming.pub/c-memory-pool-and-small-object-allocator-8f27671bd9ee https://betterprogramming.pub/c-memory-pool-and-small-object...).
• deleted 4y ago
  [deleted]
• fancyfredbot 4y ago
  NVME storage really is very fast for sequential reads, but I'd respectfully suggest that for simple tasks a Dell laptop with 1.6GB/s read speed should be bottlenecked by IO if the compute is optimised. For example SIMD-json can parse json at over 7GB/s. https://simdjson.org/ https://simdjson.org/
• prvt 4y ago
  "sorting with O(n^2) is no longer a bottleneck as we have fast processors" /s
  • itissid 4y ago
    That makes no sense. Just the brutal math of a polynomial is always going to be poor enough to notice than subpolynomial times.
    • vitiral 4y ago
      Often but not always. Cool trick: any bounded limit is always O(1)! 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.
      • Dylan16807 4y ago
        Pick a small enough bound and certain O(n^2) algorithms will behave better than certain O(n log n) algorithms. Big O notation doesn't take into account constant factors of overhead or plain old once-per-run overhead.
        • vitiral 4y ago
          Sorry it was indeed a typo
• inglor_cz 4y ago
  Hmm. I just fought with a MariaDB installation that, when set to immediate write to a disk, became rather slow. 7-8 INSERTs into a DB could easily take 3 seconds; unfortunately the internal logic of the system didn't really lend itself to one INSERT of multiple lines. Once I reconfigured innodb_flush_log_at_trx_commit to 2, the UI started being lightning fast.
• avinassh 4y ago
  I am working on a project [0] to generate 1 billion rows in SQLite under a minute and inserted 100M rows inserts in 33 seconds. First, I generate the rows and insert them in an in-memory database, then flush them to the disk at the end. To flush it to disk it takes only 2 seconds, so 99% of the time is being spent generating and adding rows to the in-memory B Tree. 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 https://github.com/avinassh/fast-sqlite3-inserts [1] - https://avi.im/blag/2021/fast-sqlite-inserts/ https://avi.im/blag/2021/fast-sqlite-inserts/
  • iamchp 4y ago
    Thank you for this (albeit a different project). My immediate question when I read the last part of the page was 'What about PyPy!?' PyPy might be different for the original post's execution, but I still assume some significant speedups?
    • avinassh 4y ago
      > PyPy might be different for the original post's execution, but I still assume some significant speedups? Yes, I believe so as well. They have done many CPU optimisations, so it is likely to be faster
• christophilus 4y ago
  Does anyone have a good resource for reasoning about how to avoid allocations in JavaScript?
• ThinkBeat 4y ago
  Is there any hardware accelerator / co processor / for the PC that will read a file into RAM autonomously mainframish and notify the OS when the file is fully loaded into memory? (bypassing the CPU entirely) Leaving the CPU to bother with other things during that time.
  • jbverschoor 4y ago
    Isn't this what a DMA controller does?
  • imtringued 4y ago
    That is how I/O works already. The problem is dealing with an asynchronous filesystem API provided by the kernel.
  • pca006132 4y ago
    You mean DMA?
  • jeroenhd 4y ago
    Do we need a coprocessor for that? Any protocol using DMA already does exactly this through interrupts or other message passing systems. 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.
    • wtallis 4y ago
      > 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. There's an interesting intermediate solution in the form of SSDs that provide a key-value interface instead of a linear block device. That gives the SSD more explicit knowledge about which chunks of data should be kept contiguous and can be expected to have the same lifetime.
• brianolson 4y ago
  SSD is pretty fast; but my app is actually trying to do more than 100_000 read-modify-write cycles per second and that still requires careful thought about the database and schema we're using. 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.
  • Agingcoder 4y ago
    Well, it depends on how far your datacenters are - in the end you're still limited by the laws of physics (speed of light). So 'fast' may actually be several ms, which might be a lot, or not a lot, depending on the problem you're trying to solve.
• SleepyMyroslav 4y ago
  the state of benchmarking by normal IT people is tragic. If one checks out his 'optimization problem statement' article [1] they can find: >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/ https://benhoyt.com/writings/count-words/
  • chakkepolja 4y ago
    Still better than obscure question from page 20 of Leetcode.
  • benhoyt 4y ago
    I'm happy to be a "normal IT person". :-) 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.
    • SleepyMyroslav 4y ago
      sry for late reply. I am glad that you are raising these topics regularly tbh. If more people stop write only coding and ask themselves questions you have asked it will be already big step forward. If they ask what profiling tools they should use it will be great. I did had a look into your article and I can not recommend limiting to tools you have used. I come from gamedev low level coding and performance analysis so I understand that my point of view is not normal xD
• daviddever23box 4y ago
  The problem here, as with most interview problems, is that it is wholly dissociated from its context; memory contraints, disk I/O, and file size are non-trivial considerations. Shame on people for stare-at-one's-shoes thinking.
  • javajosh 4y ago
    People can make reasonable assumptions for interview problems. In this case, assume the code runs on a modern developer laptop, with an SSD and lots of RAM, using some modern OS, is a fine assumption. 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.
    • LastTrain 4y ago
      But if you read the article, you would see that you'd run afoul with this interviewer doing that, because he has utterly convinced himself that I/O is no longer the bottleneck and coming to the same conclusion is your unspecified task in the interview.
• tonetheman 4y ago
  I/O is no longer the bottleneck for silly interview questions for the most part. But for real programs it can still be an issue.
• chaxor 4y ago
  It's still very bizarre to me to see people completely write off spinning platter drives as 'old tech'. They're still used everywhere! (At least in my world) We have all of my teams data on an array of 18tb drives for a 100TB raid10 setup, and a NAS at home doing the same, etc. Even some of our OS drives at work are 7200rpm drives - and we're a computational lab. Why is everyone so intent that these effectively no longer exist? The cost for a decent amount of space with NVME drives is just far too astronomical. We're not all millionaires.
  • swalsh 4y ago
    Most people are conscious that they're making a performance trade off when they decide to store data in one.
  • javajosh 4y ago
    >a 100TB raid10 setup, and a NAS at home doing the same How do you deal with these onerous constraints? Do you have a system for deciding how many copies of archive.org to keep locally?
    • fishtacos 4y ago
      I know you're being facetious, but here's some fun stats from archive.org. A few highlights from the Petabox storage system: No Air Conditioning, instead use excess heat to help heat the building. Raw Numbers as of December 2021: 4 data centers, 745 nodes, 28,000 spinning disks Wayback Machine: 57 PetaBytes Books/Music/Video Collections: 42 PetaBytes Unique data: 99 PetaBytes Total used storage: 212 PetaBytes Considering this data is from a year ago, it's got to be substantially larger now. Link: https://archive.org/web/petabox.php https://archive.org/web/petabox.php
    • deleted 4y ago
      [deleted]
    • chaxor 4y ago
      I'm not sure what exactly you mean - but we typically store DNA sequencing data from people that want us to analyze it, databases of proteins and scientific articles, ML models, etc. Proper considerations of how to store the data and compress it correctly help a lot, but unfortunately academics are pretty terrible at choosing the right data structures for the job, and often several copies are needed for mirroring the raw data, then the processed versions are updated.
• alecco 4y ago
  Nonsense. Latency matters. NVMe latency is measured in microseconds, while DRAM latency is measured in nanoseconds. Sequential processing is not that common.
  • kragen 4y ago
    latency matters but sequential processing is still most processing i hope you are doing well
• sriku 4y ago
  On a related note, John Ousterhout (in the RAMCloud project) was basically betting that the latency of accessing RAM on another computer on a fast local network will eventually become competitive to local RAM access. https://ramcloud.atlassian.net/wiki/spaces/RAM/overview https://ramcloud.atlassian.net/wiki/spaces/RAM/overview
• vitiral 4y ago
  I question the methodology. 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.
  • LastTrain 4y ago
    Thank you. I'd be pretty annoyed in this interview. Surely my potential employer would be more interested in having me apply my twenty years of real-world experiences to what I learned in CS240.
    • benhoyt 4y ago
      Not sure why you'd be annoyed? What I'm trying to gauge in my interviews is their real-world experience (not their academic CS knowledge). That's part of the reason I find my line of questioning helpful: I don't penalize them for a "wrong" answer, but more how they think about it. Then we can discuss parallelization, map-reduce techniques, profiling and measurement, and so on.
      • LastTrain 4y ago
        Annoyed because of the framing, that is: the answer isn't "wrong" in the first place.
  • Klinky 4y ago
• nkozyra 4y ago
  > Some candidates say that sorting is going to be the bottleneck, because it’s O(N log N) rather than the input processing, which is O(N). However, it’s easy to forget we’re dealing with two different N’s: the total number of words in the file, and the number of unique words. 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.
  • deleted 4y ago
    [deleted]
  • kragen 4y ago
    input processing is o(n), sorting the unique words is o(m log m) 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
    • nkozyra 4y ago
      > 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 Yeah I think this is part of my point, in that theoretical best, average and worst case scenarios can be useful in isolation but rarely tell the whole story. In the worst case, every word is unique and is equal to word count and it's a standard sorting issue.
  • burlesona 4y ago
    No. Big O tells us the theoretical best case for how the compute time will increase as the input size increases for a given algorithm. It does not say anything about the performance of a specific program on a specific input. 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.
• Mave83 4y ago
  If you have to handle multi million I/O's or files, or GB/s or TB/s bandwidth, just use DAOS.io storage. Awesome fast, scale out and self healing.
• ihatepython 4y ago
  It's true, I/O is no longer the bottleneck. The bottleneck now is interviewers who think they have the knowledge and expertise, but do not. However their authoritative position ends up distorting everything, and then said person blogs about it and causes even more problems.
  • dist1ll 4y ago
    Holy god what a burn! I absolutely agree though.
  • sublimefire 4y ago
    OMG what did I miss, please expand. What is being distorted and what problems are caused?
    • YetAnotherNick 4y ago
      Most people don't build their program for NVMe drives, but for cloud. Try benchmarking it in regular instance in AWS/GCP using default SSD and you will know that what interviewees said is true, as they are likely not building it to run a program in "your" laptop.
  • dang 4y ago
    "Don't be snarky." - https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html 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&sort=byDate&type=comment&query=share%20know%20learn%20by:dang https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor...
• tuyguntn 4y ago
  Haven't gone through the code, but measurement methodology seems wrong to me. > 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.
• svnpenn 4y ago
  > converting to lowercase in regards to accuracy, uppercase is the better option: https://stackoverflow.com/a/65433126 https://stackoverflow.com/a/65433126
  • kragen 4y ago
    there doesn't seem to be any reasoning or evidence in that post supporting "uppercase is the better option", just that uppercase produces a larger number of word classes, which might be correct or incorrect 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 'σίσυφος'
    • svnpenn 4y ago
      > there doesn't seem to be any reasoning or evidence in that post supporting "uppercase is the better option", just that uppercase produces a larger number of word classes, which might be correct or incorrect this sentence appears to be nonsense. the code doesnt check "word classes", it cases folds two characters and compares them.
      • kragen 4y ago
        character classes then
        • svnpenn 4y ago
          it doesn't check character classes either. It literally takes two characters, then uppercases both and compares, then lowercases both and compares. I have no idea where you are getting that it has anything to do with word or character classes, it doesn't.
• andrew-ld 4y ago
  Honestly I find this article too vague, and if you process large amounts of data you rarely do so with orderly reads and writes, even with databases optimized for fast disks (see rocksdb) have disks as a bottleneck even with the most recently developed hardware.
• lotik 4y ago
  Can we just give it more resources? /s
• Havoc 4y ago
  Picking something counterintuitive as interview question is not a great idea. Defeats the purpose - harder to tell whether the candidate is going with conventional wisdom because that's what they think the answer is, or because the candidate thinks that's the answer the interviewer expects. i.e. You could get sharp candidates that know the correct technical answer but intentionally give the wrong one because they rightly concluded statistically odds are the interviewer is on conventional wisdom wavelength. Could be good if you're specifically looking for someone good at mindgames I guess
  • deleted 4y ago
    [deleted]
  • LastTrain 4y ago
    And then compound that by your counterintuitive assertion being generally wrong in most useful cases. He is either interviewing very junior candidates or frustrating a lot of people.
• joshspankit 4y ago
  In the last few years I’ve been quietly moving database “rows” from databases to the disk. Back in the day accessing data from MySQL was actually slower than current SSD speeds. And now you can get all sorts of benefits for free: hard link deduplication, versioning, live backup, easy usage of GNU tools... I don’t discuss this with certain types of colleagues, but the results are excellent.
• notacoward 4y ago
  Interesting observation, but I think the author crosses a bridge too far here. > 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.
  • kragen 4y ago
    the author is evidently pretty unskilled and unaware of it in a lot of ways, this being one of them
• iAm25626 4y ago
  IO also meant network to me. Often the target(database, or device generating telemetry) is 10+ms away. That round trip time is bottle neck by physics(speed of light). side benefit of sqlite being local file system/memory.
• deleted 4y ago
  [deleted]
• hansvm 4y ago
  I/O is still often the bottleneck. My laptop can handle 11 GB/s through RAM (and no NVME, so under 1 GB/s through the hard drive), less with unpredictable I/O patterns (like a hash-map) and 7600 GB/s through the CPU. Unless the thing you're doing is particularly expensive per byte of data, you're going to be limited at a minimum by RAM I/O, and maybe by DISK I/O. 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.
• btbuildem 4y ago
  As it often goes with these types of interview questions, there's a lot of context missing. What is the goal? Do we want readable code? Do we want fast code? Are we constrained somehow? It seems here the author doesn't really know, but kudos to them for examining their assumptions. As a side note, a trie would be a neat data structure to use in a solution for this toy problem.
• 323 4y ago
  Further evidence is the fact that optimized SIMD JSON or UTF8 libraries exist. If I/O was the bottleneck, there wouldn't be a need to parse JSON using SIMD.
• nanis 4y ago
  Related posts from my past experience from about 10 years ago: * 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.html https://www.nu42.com/2013/02/splitting-long-lines-is-slow.ht... [2]: https://www.nu42.com/2012/04/can-parallelforkmanager-speed-up.html https://www.nu42.com/2012/04/can-parallelforkmanager-speed-u...
• vinay_ys 4y ago
  Storage and compute separation is key to scaling data workloads. Here, scaling could be w.r.t volume/shape of data, number of concurrent jobs on the same dataset, complexity of each job etc. In such an architecture, network access is unavoidable. And, to if you have multiple jobs competing for access to the same dataset concurrently, your sequential access can turn into semi-random access. You also have concerns about utilization of resources while being scalable w.r.t arbitrary bursty contentious workloads. These are the things that make it complex w.r.t managing IO resources.
• slotrans 4y ago
  Article itself is fine but the "conclusion" is loony. You can't draw conclusions about big data from toy experiments with small data.
• edejong 4y ago
  "Optimised" code according to the author. What can we do to optimise further? - 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-language-processing-in-python/regular-expressions-word-tokenization?ex=10 https://campus.datacamp.com/courses/introduction-to-natural-...
  • morelisp 4y ago
    > thread pool 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.
    • Dylan16807 4y ago
      > 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.) You could use one big buffer for all your words. Arguably that's bump allocation but it's much simpler than malloc.
• lmeyerov 4y ago
  I like the author started with measuring and thinking bandwidth, which makes sense for streaming through a big file, so I'd have continued that way towards a diff design & conclusion 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.
• up2isomorphism 4y ago
  The correct way to describe his experiment should be: Of course I/O is the slowest, but it is fast enough to let most of the programmers not able to fully utilize it.
• dehrmann 4y ago
  I'm not surprised. I've seen bulk MySQL reads in Python be CPU-bound. The interesting followup was that parallelizing reads in subprocesses wasn't going to help much because I'd get killed by CPU again when serializing/deserializing between processes. I was capped at a ~2x speedup.
• mastax 4y ago
  I was recently working on parsing 100K CSV files and inserting them into a database. The files have a non-column-oriented header and other idiosyncrasies so they can't be directly imported easily. They're stored on an HDD so my first instinct was to focus on I/O: read the whole file into memory as an async operation so that there are fewer larger IOs to help the HDD and so that other parser tasks can do work while waiting for the read to complete. I used a pretty featureful C# CSV parsing library which did pretty well on benchmarks [0] (CsvHelper) so I wasn't really worried about that part. 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-parsers https://www.joelverhagen.com/blog/2020/12/fastest-net-csv-pa...
• mikesabbagh 4y ago
  Usually we mainly run jobs on nfs or similar disks. I/O time would be more significant. Would be nice to run thoses tests on aws
• Dunedan 4y ago
  As the algorithm used in the example is straight-forward I figured that using UNIX command line tools might be an even simpler way to implement it. Here is what I came up with: time cat kjvbible_x100.txt | tr "[:upper:] " "[:lower:]\n" | sort --buffer-size=50M | uniq -c | sort -hr > /dev/null On my machine this turned out to be ~5 times slower than the provided Python implementation. Nearly all of the time is spent in the first invocation of `sort`. Further increasing the buffer size doesn't make a significant difference. I also played around with the number of threads `sort` uses, but didn't see any improvement there either. 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?
  • benhoyt 4y ago
    It's because that first invocation of sort is sorting the entire input (413MB), not just the unique words (less than a MB). The sort is probably O(NlogN), but that's a big N. Counting by inserting into a hash table is much faster, at O(N).
  • aljarry 4y ago
    It looks like you're sorting the whole file, while python implementation sorts only unique values.
  • mastax 4y ago
    `sort | uniq` is really slow for this, as it has to sort the entire input first. I use `huniq` which is way faster for this. I'm sure there are many similar options. https://github.com/koraa/huniq https://github.com/koraa/huniq
  • zackmorris 4y ago
    Dangit, I'm supposed to be doing yardwork today so you hijacked my procrastination motivation haha! 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
• mips_avatar 4y ago
  I/O is sometimes the bottleneck. On Windows any operation with lots of small file operations bottlenecks on NTFS and Defender operations. It makes some applications like git that run beautifully on Linux need to take some countermeasures to operate well on Windows.
• kgeist 4y ago
  The most common performance problems I've encountered in our projects are: 1) lack of indexes resulting in extensive table scans 2) I/O calls in a loop without batching. I don't know if it counts as "I/O bottlenecks" or not.
• Klinky 4y ago
  The Samsung PM9A1 is the OEM version of the 980 Pro, a top-tier PCIe 4.0 NVME SSD. What about an older SATA SSD(one without DRAM buffer or HMB), or a 5400RPM hard drive? Also as others have pointed out, random I/O will tank perf, especially simultaneous r/w operations to the same media.
• kazinator 4y ago
  Processing cache hot data has never been the bottleneck. 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.
• therealbilly 4y ago
  Does any of this really matter?