An overengineered solution to `sort | uniq -c` with 25x throughput (hist)

57 pointsposted 4 days ago
by noamteyssier
(github.com)

31 Comments

zX41ZdbW

2 hours ago

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

gigatexal

9 minutes ago

Exactly. I love this and DuckDb and other such amazing tools.

nasretdinov

2 hours ago

To be more fair you could also add SETTINGS max_threads=1 though?

supermatt

an hour ago

How is that “more fair”?

nasretdinov

37 minutes ago

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

34 minutes ago

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.

f311a

8 minutes ago

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.

jll29

21 minutes ago

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

4 minutes ago

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

4 minutes 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?

noamteyssier

4 days ago

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

theemptiness

2 hours ago

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

2 hours ago

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

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

dbdr

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

nasretdinov

2 hours ago

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

donatj

an hour ago

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

Someone

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

ukuina

an hour ago

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.

scaredginger

an hour ago

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.

vlovich123

2 hours ago

Why does this test against sort | uniq | sort? It’s kind of weird to sort twice no?

gucci-on-fleek

2 hours ago

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

Aaron2222

2 hours ago

  sort | uniq -c | sort -n
The second sort is sorting by frequency (the count output by `uniq -c`).

BuildTheRobots

2 hours ago

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

2 hours ago

more precisely, uniq produces output in the same order as the input to it, just collapsing runs / run-length encoding it

flowerthoughts

3 hours ago

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

2 hours ago

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

2 hours ago

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

2 hours ago

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.