[HN Gopher] An overengineered solution to `sort | uniq -c` with ...
___________________________________________________________________
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)(tm) 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
Author : noamteyssier
Score : 108 points
Date : 2025-10-22 22:26 UTC (5 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| southwindcg wrote:
| I don't [currently?] have a use case for this tool, but I love
| seeing existing tools made faster or more efficient.
| noamteyssier wrote:
| I 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 wrote:
| Oh, 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.
| mfld wrote:
| Nice - thanks! I assume the non-naive implementations skip the
| sorting and instead hash the input lines?
| flowerthoughts wrote:
| The 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 wrote:
| To 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 wrote:
| I'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.
| thaumasiotes wrote:
| That'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 wrote:
| Why does this test against sort | uniq | sort? It's kind of weird
| to sort twice no?
| BuildTheRobots wrote:
| It'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 wrote:
| more precisely, uniq produces output in the same order as the
| input to it, just collapsing runs / run-length encoding it
| Aaron2222 wrote:
| sort | uniq -c | sort -n
|
| The second sort is sorting by frequency (the count output by
| `uniq -c`).
| gucci-on-fleek wrote:
| The 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 wrote:
| `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 wrote:
| Small 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 wrote:
| We 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 wrote:
| > 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 wrote:
| The 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 wrote:
| > 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 wrote:
| > 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 wrote:
| Yes, it's used just for writing
| zX41ZdbW wrote:
| This 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-...
| nasretdinov wrote:
| To be more fair you could also add SETTINGS max_threads=1
| though?
| supermatt wrote:
| How is that "more fair"?
| nasretdinov wrote:
| Well, 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 wrote:
| Last time I checked, writing efficient, contention-free
| and correct parallel code is hard and often harder than
| pulling an algorithm out of a book.
| reppap wrote:
| Would you take half the wheels off a car to compare it to
| a motorcycle?
| Almondsetat wrote:
| Motorcycles are faster than cars though
| Etheryte wrote:
| Not necessarily, that really depends on what you mean by
| fast. Cars definitely go higher in top speed than bikes
| do for example. If I'm not mistaken, racing electric cars
| also accelerate comparable or faster than bikes. A bike
| can generally go around a track faster than a car, but
| that only holds true in dry conditions. Etc, many ways to
| define fast and what you actually mean.
| AtlasBarfed wrote:
| I thought all the land speed records were basically
| motorcycles.
|
| Jet motorcycles but motorcycles
| wang_li wrote:
| Musk's roadster is currently going in excess of 10,000
| mph. Which bike is faster than that? :)
| gigatexal wrote:
| Exactly. I love this and DuckDb and other such amazing tools.
| da_chicken wrote:
| I'd not heard of clickhouse before. It does seem interesting,
| but I just can't get behind a project that says:
|
| > The easiest way to download the latest version is with the
| following command:
|
| > curl https://clickhouse.com/ | sh
|
| Like, sure, there is some risk downloading a binary or running
| an arbitrary installer. But this is just nuts.
| gigatexal wrote:
| Chdb is just a binary. You can just grab that. Also pipe to
| sh is used by a ton of projects
| bflesch wrote:
| it's used by many projects but still regarded as an anti-
| pattern and security issue
| Etheryte wrote:
| A ton of people drink and drive too, doesn't make it any
| more fine.
| gigatexal wrote:
| Y'all are so pure. Just don't install it that way.
| Sheesh.
| Aefiam wrote:
| how is this any less secure than running a binary/installer?
| the binary could run this inside?
| trollbridge wrote:
| It's Apache licenced and you could also install it via your
| favourite package installer. Given all the crazy supply chain
| attacks going on, I don't really feel this is any worse than
| downloading a binary from a distro archive, and specifically
| this pipe | sh doesn't expect you to run it as root (which a
| lot of other cut-and-paste installers do).
| xorcist wrote:
| > I don't really feel this is any worse than downloading a
| binary from a distro archive
|
| Please don't say that. It denigrates the work of all the
| packagers that actually keep our supply chains clean. At
| least in the major distributions such as Red Hat/Fedora and
| Debian/Ubuntu.
|
| The distro model is far from perfect and there are still
| plenty of ways to insert malware into the process, but it
| certainly is far better than running binaries directly from
| a web page. You have no idea who have access to that page
| and its mirrors and what their motives are. The binary
| isn't even signed, let alone reviewed by anyone!
| monerozcash wrote:
| >Like, sure, there is some risk downloading a binary or
| running an arbitrary installer. But this is just nuts.
|
| It's literally exactly the same thing
| nsteel wrote:
| Just noting that in your benchmark (which we know nothing
| about), your "naive" data point is just 2.29x slower than hist.
| In their testing it was 27x slower! And it's not quite the same
| naive shell command, which isn't helpful.
| danlark1 wrote:
| Disclaimer: the author of the comment is the founder and CTO of
| ClickHouse
| edoceo wrote:
| Disclosure, not disclaimer.
|
| They want to own the claims made.
| danlark1 wrote:
| Yes, sorry, it should be "disclosure"
| OJFord wrote:
| And all their comments are shilling Clickhouse either
| directly or via a project built on top of it, without
| disclosure.
| tuukkah wrote:
| Considering that it's an open source tool, I don't know if
| it's that bad to be shilling for the commons, basically.
| LtdJorge wrote:
| When using clickhouse-local like this, does it build a logical
| plan and run the optimizer on it? Does it have any kind of code
| generation, since it knows the query (and physical data layout)
| ahead of time?
| nasretdinov wrote:
| Note 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
| noctune wrote:
| I 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
| Someone wrote:
| > 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...)
| donatj wrote:
| I 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
| scaredginger wrote:
| Looks like the impl uses a HashMap. I'd be curious about how a
| trie or some other specialized string data structure would
| compare here.
| ukuina wrote:
| Neat!
|
| 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.
| majke wrote:
| I thought my mmuniq holds the crown!
|
| https://blog.cloudflare.com/when-bloom-filters-dont-bloom/
|
| https://github.com/majek/mmuniq
| nasretdinov wrote:
| I believe, given its reliance on the Bloom filter, that it
| doesn't actually report occurrences count?
| jll29 wrote:
| I 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 wrote:
| This 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 wrote:
| > 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 wrote:
| One 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://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...
| [2]
| https://github.com/NetBSD/src/blob/7d8184e/share/mk/bsd.lib....
| mr_toad wrote:
| Sounds like it's intended to be used to schedule jobs, or
| complex builds.
| pbhjpbhj wrote:
| I'm sure you're doing it in a sensible way, but... the thought
| that played out in my head went a little like this {apologies,
| I'm not well today, this might be a fever dream}:
|
| Interviewer: "Welcome to your hammer-stuff interview, hope
| you're ready to show your hammering skills, we see from your
| resume you've been hammering for a while now."
|
| Schmuck: "Yeah, I just love to make my bosses rich by hammering
| things!"
|
| Interviewer: "Great, let's get right into the hammer use ...
| here's a screw, show me how you'd hammer that."
|
| Schmuck: (Thinks - "Well, of course, I wouldn't normally hammer
| those; but I know interviewers like to see weird things
| hammered! Here goes...")
|
| [Hammering commences]
|
| Interviewer: "Well thanks for flying in, but you've failed the
| interview. We were very impressed that you demonstrated some of
| the best hammering we've ever seen. But, of course, wanted to
| see you use a screwdriver here in your hammering interview at
| We Hammer All The Things."
| rs186 wrote:
| Your loss, not theirs. Lots of good developers are not expert
| at unix commands, many of which spend most of their time on
| Windows. They may be "wasting" 2 minutes on this specific task
| with their "inefficient" method, but they may perform much
| better on other tasks, to the point that 2 minutes saved here
| is nothing.
|
| Not to mention that these days people often ask ChatGPT "what's
| the best way to do this" before proceeding, and whatever you
| ask in interviews is completely irrelevant.
|
| It is exactly for these reasons we never ask such questions in
| our interviews. There are much more important aspects of a
| candidate to evaluate.
| Aefiam wrote:
| you can develop just as fast or even faster with python once
| you develop a good enough utility library for it.
|
| For example my python interpreter imports my custom List and
| Path classes and I could just do the following to get the same
| result:
|
| List(List(Path("filepath").read_text_file().splitlines()).group
| _by_key(lambda x:x).items()).map(lambda
| x:(len(x[1]),x[0])).sorted()
|
| and if used often enough, it could made an utility method:
|
| Path("filepath").read_sorted_by_most_common()
|
| So I find it shortsighted to reject someone based on that
| without giving them a chance to explain their reasoning.
|
| I think generally people really underestimate how much more
| productive you can be with a good utility library.
| zahlman wrote:
| > For example my python interpreter imports my custom List
| and Path classes and I could just do the following to get the
| same result: List(List(Path("filepath").read_
| text_file().splitlines()).group_by_key(lambda
| x:x).items()).map(lambda x:(len(x[1]),x[0])).sorted()
|
| ... But I don't know why you would, because with builtins and
| the standard library you can already do
| sorted((count, line) for (line, count) in
| Counter(Path("filepath").read_text().splitlines()).items())
|
| > and if used often enough, it could made an utility method:
|
| Sure, but you can do that for any functionality in any
| practical language.
| f311a wrote:
| People 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.
| fsiefken wrote:
| I'm curious how much faster this is compared to the rust uutils
| coreutils ports of sort and uniq
| G_o_D wrote:
| why no mention of awk ? awk '!a[$0]++'
| ashvardanian wrote:
| Storage, 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-
| fil...
|
| [1] https://github.com/ashvardanian/StringWars?tab=readme-ov-
| fil...
| trollbridge wrote:
| This 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
| MontyCarloHall wrote:
| >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 naive
| `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
|
| [*] Birthday problem math says about 250, for 50M strings sampled
| from a pool of ~1T.
| pclmulqdq wrote:
| The 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.
| xorcist wrote:
| From 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.
| stackedinserter wrote:
| It'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 wrote:
| But GNU coreutils would reject a new flag, you'd need to add it
| to BSD or Rust uutils.
| zahlman wrote:
| How 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 wrote:
| Reasonably often in ETL type tasks.
___________________________________________________________________
(page generated 2025-10-27 23:02 UTC)