9 ms·
An overengineered solution to `sort | uniq -c` with 25x throughput (hist)
Was sitting around in meetings today and remembered an old shell script I had to count the number of unique lines in a file. Gave it a shot in rust and with a little bit of (over-engineering)™ I managed to get 25x throughput over the naive approach using coreutils as well as improve over some existing tools.
Some notes on the improvements:
1. using csv (serde) for writing leads to some big gains
2. arena allocation of incoming keys + storing references in the hashmap instead of storing owned values heavily reduced the number of allocations and improves cache efficiency (I'm guessing, I did not measure).
There are some regex functionalities and some table filtering built in as well.
happy hacking
- mfld 11mo agoNice - thanks! I assume the non-naive implementations skip the sorting and instead hash the input lines?
- noamteyssier 11mo agoyeah that's right - there are trade-offs in doing so as it can require much more memory. So like everything it's an application specific decision
- deleted 1y ago[deleted]
- southwindcg 11mo agoI don't [currently?] have a use case for this tool, but I love seeing existing tools made faster or more efficient.
- noamteyssier 11mo agoI think that it's a pretty common use case for text processing - I end up needing to use it a lot in bioinformatics where there is a lot of text processing. It's great when you quickly need to see what the distribution of classes in an input stream is. This pops up all the time. Like measuring different types of log messages, counting the variants of a field in a csv, finding the most common word or substring, etc.
- southwindcg 11mo agoOh, I meant me, personally, I don't have a use case for it. Without a doubt a lot of people are going to find this speed improvement valuable.
- flowerthoughts 11mo agoThe win here might be using HashMap to avoid having to sort all entries. Then sorting at the end instead. What's the ratio of duplicates in the benchmark input? There is no text encoding processing, so this only works for single byte encodings. That probably speeds it up a little bit. Depending on the size of the benchmark input, sort(1) may have done disk-based sorting. What's the size of the benchmark input?
- wodenokoto 11mo agoTo me, the really big win would be _not_ to have to sort at all. Have an option to keep first or last duplicate and remove all others while keeping line order is usually what I need.
- mabster 11mo agoI've written this kind of function so many times it's not funny. I usually want something that is fed from an iterator, removes duplicates, and yields values as soon as possible.
- noamteyssier 11mo agoI've added this functionality to `hist-0.1.5` with a benchmark of other tools that do this on the CLI
- thaumasiotes 11mo agoThat's easy to do if you're keeping the first duplicate. It becomes complex if you're keeping the last duplicate, because every time you find a duplicate you have to go back through your "output" and delete the earlier occurrence. You could do an annotating pass for learning which of each line is the last one, and then a followup pass for printing (or otherwise echoing) only the lines that are the last of their kind. Technically still faster than sorting. You could also keep the information on last occurrence of each line in the hash map (that's where it's going to be anyway), and once you're done with the first pass sort the map by earliest last occurrence. That will get you the lines in the right order, but you had to do a sort. If the original input was mostly duplicates, this is probably a better approach. You could also track last occurrence of each line in a separate self-sorting structure. Now you have slightly more overhead while processing the input, and sorting the output is free.
- vlovich123 11mo agoWhy does this test against sort | uniq | sort? It’s kind of weird to sort twice no?
- BuildTheRobots 11mo agoIt's something I've done myself in the past. First sort is because it needs to be sorted for uniq -c to count it proper, second sort because uniq doesn't always give the output in the right order.
- evertedsphere 11mo agomore precisely, uniq produces output in the same order as the input to it, just collapsing runs / run-length encoding it
- Aaron2222 11mo agosort | uniq -c | sort -n The second sort is sorting by frequency (the count output by `uniq -c`).
- emmelaich 11mo agoI often add `head` with `sort -rn` because I'm only interested in the largest.
- gucci-on-fleek 11mo agoThe first "sort" sorts the input lines lexicographically (which is required for "uniq" to work); the second "sort" sorts the output of "uniq" numerically (so that lines are ordered from most-frequent to least-frequent): $ echo c a b c | tr ' ' '\n' c a b c $ echo c a b c | tr ' ' '\n' | sort a b c c $ echo c a b c | tr ' ' '\n' | sort | uniq -c 1 a 1 b 2 c $ echo c a b c | tr ' ' '\n' | sort | uniq -c | sort -rn 2 c 1 b 1 a
- happysadpanda2 11mo ago`uniq -c` introduces a "count" at the beginning of the line, so what we are then sorting is on frequency of the unique terms in the output, not sorting the unique terms again (which indeed would be kindof nonsensical)
- theemptiness 11mo agoSmall semantics nit: it is not overengineered, it is engineered. You wanted more throughput, the collection of coreutils tools was not designed for throughput but flexibility. It is not difficult to construct scenarios where throughput matters but that IMHO that does not determine engineering vs overengineering. What matters is whether there are requirements that need to be met. Debating the requirements is possible but doesn't take away from whether a solution obtained with reasonable effort meets the spec. Overengineering is about unreasonable effort, which could lead to overshoot the requirements, not about unreasonable requirements.
- mabster 11mo agoWe had similar thoughts about "premature optimisation" in the games industry. That is it's better to have prematurely optimised things than finding "everything is slow". But I guess in that context there are many many "inner-most loops" to optimise.
- chii 11mo ago> That is it's better to have prematurely optimised things than finding "everything is slow". or you found that you've optimized a game that is unfun to play and thus doesn't sell, even tho it runs fast...
- wongarsu 11mo agoThe best-practice solution would be to write a barely optimized ugly prototype to make sure the core idea is fun, then throw away the prototype and write the "real" game. But of course that's not always how reality works
- chii 11mo ago> not always how reality works yep. The stakeholder (who is paying the money) asks why the prototype can't just be "fixed up" and be sold for money, instead of paying for more dev time to rewrite. There's no answer that they can be satisfied with.
- dbdr 11mo ago> using csv (serde) for writing leads to some big gains Could you explain that, if you have the time? Is that for writing the output lines? Is actual CSV functionality used? That crate says "Fast CSV parsing with support for serde", so I'm especially confused how that helps with writing.
- LtdJorge 11mo agoYes, it’s used just for writing
- noamteyssier 11mo agoYeah I'm using it to serialize the output lines as a TSV. Rust's `println!` is notoriously slow and using `csv` to serialize the output is a nice way to boost throughput
- dbdr 11mo agoThanks. Nice find! Though it feels weird to have to use a csv crate for that. Ideally the `fast printing` part should be understood, and either used directly, or extracted as a separate, smaller crate.
- zX41ZdbW 11mo agoThis and similar tasks can be solved efficiently with clickhouse-local [1]. Example: ch --input-format LineAsString --query "SELECT line, count() AS c GROUP BY line ORDER BY c DESC" < data.txt I've tested it and it is faster than both sort and this Rust code: time LC_ALL=C sort data.txt | uniq -c | sort -rn > /dev/null 32 sec. time hist data.txt > /dev/null 14 sec. time ch --input-format LineAsString --query "SELECT line, count() AS c GROUP BY line ORDER BY c DESC" < data.txt > /dev/null 2.7 sec. It is like a Swiss Army knife for data processing: it can solve various tasks, such as joining data from multiple files and data sources, processing various binary and text formats, converting between them, and accessing external databases. [1] https://clickhouse.com/docs/operations/utilities/clickhouse-local https://clickhouse.com/docs/operations/utilities/clickhouse-...
- nasretdinov 11mo agoTo be more fair you could also add SETTINGS max_threads=1 though?
- supermatt 11mo agoHow is that “more fair”?
- deleted 11mo ago[deleted]
- nasretdinov 11mo agoWell, fair in a sense that we'd compare which implementation is more efficient. Surely, ClickHouse is faster, but is it because it's using actually superior algorithms or is it just that it executes stuff in parallel by default? I'd like to believe it's both, but without "user%" it's hard to tell
- mickeyp 11mo agoLast time I checked, writing efficient, contention-free and correct parallel code is hard and often harder than pulling an algorithm out of a book.
- nasretdinov 11mo agoNote that by default sort command has a pretty low memory usage and spills to disk. You can improve the throughput quite a bit by increasing the allowed memory usage: --buffer-size=SIZE
- noamteyssier 11mo agoI didn't know that - I've added in buffer size with a fairly large buffer to the benchmarks as well
- noctune 11mo agoI built something similarly a few years ago for `sort | uniq -d` using sketches. The downside is you need two passes, but still it's overall faster than sorting: https://github.com/mpdn/sketch-duplicates https://github.com/mpdn/sketch-duplicates
- Someone 11mo ago> I am measuring the performance of equivalent cat <file> | sort | uniq -c | sort -n functionality. It likely won’t matter much here, but invoking cat is unnecessary. sort <file> | uniq -c | sort -n will do the job just fine. GNU’s sort also has a few flags controlling buffer size and parallelism. Those may matter more (see https://www.gnu.org/software/coreutils/manual/html_node/sort-invocation.html#sort-invocation https://www.gnu.org/software/coreutils/manual/html_node/sort...)
- deleted 11mo ago[deleted]
- noamteyssier 11mo agoThanks for sharing! You're right that the `cat` is unnecessary - and removing it actually had some marginal gains to the naive solution. I've updated the benchmarks to show this Cheers
- donatj 11mo agoI created "unic" a number of years ago because I had need to get the unique lines from a giant file without losing the order they initially appeared. It achieves this using a Cuckoo Filter so it's pretty dang quick about it, faster than sorting a large file in memory for sure. https://github.com/donatj/unic https://github.com/donatj/unic
- deleted 11mo ago[deleted]
- noamteyssier 11mo agoNice tool!
- noamteyssier 11mo agoI've actually added a benchmark for this specific task and added `unic` to it. It may not be the most fair comparison because with these random fastqs I'm generating the vast majority of the input is unique so it could be overloading the cuckoo filter.
- ukuina 11mo agoNeat! Are there any tools that tolerate slight mismatches across lines while combining them (e.g., a timestamp, or only one text word changing)? I attempted this with a vector DB, but the embeddings calculation for millions of lines is prohibitive, especially on CPU.
- scaredginger 11mo agoLooks like the impl uses a HashMap. I'd be curious about how a trie or some other specialized string data structure would compare here.
- noamteyssier 11mo agoI think this could potentially really reduce the amount of memory required - especially in cases where there is a lot of repetitive prefixes. Would be interesting to try this out
- majke 11mo agoI thought my mmuniq holds the crown! https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ https://github.com/majek/mmuniq https://github.com/majek/mmuniq
- nasretdinov 11mo agoI believe, given its reliance on the Bloom filter, that it doesn't actually report occurrences count?
- noamteyssier 11mo agothis looks very interesting and I'd love to add it to the benchmarking! I was interested in trying it but unfortunately got an installation error on my macbook where I'm running the benchmarks: ``` clang \ -g -ggdb -O3 \ -Wall -Wextra -Wpointer-arith \ -D_FORTIFY_SOURCE=2 -fPIE \ mmuniq.c \ -lm \ -Wl,-z,now -Wl,-z,relro \ -o mmuniq mmuniq.c:1:10: fatal error: 'byteswap.h' file not found 1 | #include <byteswap.h> | ^~~~~~~~~~~~ 1 error generated. make: ** [mmuniq] Error 1 ```
- jll29 11mo agoI use questions around this pipeline in interviews. As soon as people say they'd write a Python program to sort a file, they get rejected. Arguably, this will result in a slower result in most cases, but the reason for the rejection is wasting developer time (not to mention time to test for correctness) to re-develop something that is already available in the OS.
- f311a 11mo agoThis depends on the context... If a file is pretty small, I would avoid sort pipes when there is a Python codebase. It's only useful when the files are pretty big (1-5GB+) They are tricky and not very portable. Sorting depends on locales and the GNU tools implementation.
- coldstartops 11mo ago> Wasting developer time What is the definition of wasting developer time? If a developer takes a 2 hours break to recover mental power and avoid burnout, is it considered time wasted?
- wahern 11mo agoOne of the cooler Unix command utilities is tsort, which performs a topological sort. Basically you give it a list of items (first word in each line) and their dependencies (subsequent words on each line) and it sorts them accordingly, similar to how, e.g., Make builds a graph of targets and dependencies to run recipes in the correct order. https://en.wikipedia.org/wiki/Tsort https://en.wikipedia.org/wiki/Tsort https://pubs.opengroup.org/onlinepubs/9799919799/utilities/tsort.html https://pubs.opengroup.org/onlinepubs/9799919799/utilities/t... However, I've never found a use for it. Apparently it was written for the Version 7 Unix build system to sort libraries for passing to the linker. And still used.[1][2] But of the few times I've needed a topological sort, it was part of a much larger problem where shell scripting was inappropriate, and implementing it from scratch using a typical sort routine isn't that difficult. Still, I'm waiting for an excuse to use it someday, hopefully in something high visibility so I can blow people's minds. [1] https://github.com/openbsd/src/blob/17290de/share/mk/bsd.lib.mk#L191 https://github.com/openbsd/src/blob/17290de/share/mk/bsd.lib... [2] https://github.com/NetBSD/src/blob/7d8184e/share/mk/bsd.lib.mk#L533 https://github.com/NetBSD/src/blob/7d8184e/share/mk/bsd.lib....
- deleted 11mo ago[deleted]
- f311a 11mo agoPeople often use sort | uniq when they don't want to load a bunch of lines into memory. That's why it's slow. It uses files and allocates very little memory by default. The pros? You can sort hundreds of gigabytes of data. This Rust implementation uses hashmap, if you have a lot of unique values, you will need a lot of RAM.
- noamteyssier 11mo agoYeah definitely, it's always a trade-off. I think in many cases where I use it especially the number of unique values is actually not crazy high (much less than the required RAM) and the number of lines is crazy high. So in those settings I think it's absolutely worth it
- fsiefken 11mo agoI'm curious how much faster this is compared to the rust uutils coreutils ports of sort and uniq
- noamteyssier 11mo agoGood question! I just added that comparison and the rust uutils coreutils port is significantly faster than the standard coreutils.
- G_o_D 11mo agowhy no mention of awk ? awk '!a[$0]++'
- noamteyssier 11mo agoI've added awk into the benchmarks also!
- pabs3 11mo agoAlso perl, should be faster than awk IIRC: perl -ne 'print if ! $a{$_}++'
- ashvardanian 11mo agoStorage, strings, sorting, counting, bioinformatics... I got nerd-sniped! Can't resist a shameless plug here :) Looking at the code, there are a few things I would consider optimizing. I'd start by trying (my) StringZilla for hashing and sorting. HashBrown collections under the hood use aHash, which is an excellent hash function, but on both short and long inputs, on new CPUs, StringZilla seems faster [0]: short long aHash::hash_one 1.23 GiB/s 8.61 GiB/s stringzilla::hash 1.84 GiB/s 11.38 GiB/s A similar story with sorting strings. Inner loops of arbitrary length string comparisons often dominate such workloads. Doing it in a more Radix-style fashion can 4x your performance [1]: short long std::sort_unstable_by_key ~54.35 M compares/s 57.70 M compares/s stringzilla::argsort_permutation ~213.73 M compares/s 74.64 M compares/s Bear in mind that "compares/s" is a made-up metric here; in reality, I'm comparing from the duration. [0] https://github.com/ashvardanian/StringWars?tab=readme-ov-file#hash https://github.com/ashvardanian/StringWars?tab=readme-ov-fil... [1] https://github.com/ashvardanian/StringWars?tab=readme-ov-file#sequence-operations https://github.com/ashvardanian/StringWars?tab=readme-ov-fil...
- noamteyssier 11mo agoCool suggestions! I definitely would be interested in exploring other hash functions for this (and other binf works) so I'll definitely take a look at your stringzilla lib.
- trollbridge 11mo agoThis reminds me of a program I wrote to do the same thing that wc -L does, except a lot faster. I had to run it on a corpus of data that was many gigabytes (terabytes) in size, far too big to fit in RAM. MIT license. https://github.com/JoshRodd/mll https://github.com/JoshRodd/mll
- MontyCarloHall 11mo ago>I use nucgen to generate a random 100M line FASTQ file and pipe it into different tools to compare their throughput with hyperfine. This is a strange benchmark [0] -- here is what this random FASTQ looks like: $ nucgen -n 100000000 -l 20 | head -n8 >seq.0 TGGGGTAAATTGACAGTTGG >seq.1 CTTCTGCTTATCGCCATGGC >seq.2 AGCCATCGATTATATAGACA >seq.3 ATACCCTAGGAGCTTGCGCA There are going to be very few [*] repeated strings in this 100M line file, since each >seq.X will be unique and there are roughly a trillion random 4-letter (ACGT) strings of length 20. So this is really assessing the performance of how well a hashtable can deal with reallocating after being overloaded. I did not have enough RAM to run a 100M line benchmark, but the following simple `awk` command performed ~15x faster on a 10M line benchmark (using the same hyperfine setup) versus the naïve `sort | uniq -c`, which isn't bad for something that comes standard with every *nix system. awk '{ x[$0]++ } END { for(y in x) { print y, x[y] }}' <file> | sort -k2,2nr [0] https://github.com/noamteyssier/hist-rs/blob/main/justfile https://github.com/noamteyssier/hist-rs/blob/main/justfile [*] Birthday problem math says about 250, for 50M strings sampled from a pool of ~1T.
- pclmulqdq 11mo agoThe awk script is probably the fastest way to do this still, and it's faster if you use gawk or something similar rather than default awk. Most people also don't need ordering, so you can get away with only the awk part and you don't need the sort.
- noamteyssier 11mo agoTotally agree it's a bit of weird benchmark - it was just the first thing that I thought of to generate a huge amount of lines to test throughput. There are definitely other benchmarks that we could try as well to test other characteristics as well. I've actually just added in this `awk` implementation you provided to the benchmarks well. Cheers!
- xorcist 11mo agoFrom a causal glance, isn't your code limited by the amount of available memory? Which could be totally useful in itself, but not even close to what "sort" is doing. Did you run sort with a buffer size larger than the data? Your specialized one-pass program is likely faster, but at least the numbers would mean something. That said, I don't see what is over-engineered here. It's pretty straightforward and easy to read.
- noamteyssier 11mo agoYes you're right, it's not trying to do what `sort` is doing, it's trying to reproduce the output of `sort | uniq -c | sort -n` which is a more specialized but common task. But you're right - it will be limited by RAM in a way the unix tools are not. I did add a test with sort using a larger buffer size to the benchmarks as well.
- stackedinserter 11mo agoIt's shame that we normalized sorting twice for these cases. Somebody, implement `uniq --global` switch already. Put it into your resume, it's a legitimate thing to brag about.
- rurban 11mo agoBut GNU coreutils would reject a new flag, you'd need to add it to BSD or Rust uutils.
- zahlman 11mo agoHow often is "count the unique lines of a file" a realistic task for others out there, and how big of files do y'all need to process and why?
- Tostino 11mo agoReasonably often in ETL type tasks.
- noamteyssier 11mo agoShows up a lot in bioinformatics actually - trying to identify sequences with a specific subsequence (grep) and how many of each unique sequence there are. The number of lines here could be massive (order of 1-10's of GB) You don't really end up using these results in any specific analysis but it's super helpful for troubleshooting tools or edge-cases.
- saltcured 11mo agoBack in the day, optimizing this would be about parallel IO and some map-reduce processing. Data sharded on a bunch of nodes, each effectively doing "sort | uniq -c" and then doing a merge of those sorted counts. And then there would be countless arguments about whether you have to count the time it takes to stage the data into the cluster as part of the task completion benchmark...
- noamteyssier 11mo agoI think you'd still need to go through that if you were really optimizing both `sort` and `uniq` working with their constraints. What I'm really optimizing here is the functional equivalent of `sort | uniq -c | sort -n`