Hacker News Reader

Comment by justinsaccount | Hacker News Reader

'sort | uniq -c | sort -n' is an interesting pipeline. It will always work and does a great job with large cardinality data on low memory systems.

However, if you have the ram, or know the data set has a low cardinality (like, http status codes or filesnames instead of ip addresses) then something that works in memory will be much more efficient.

I threw 144,000,000 'hello' and 'world' into a file:

  justin@box:~$ ls -lh words
  -rw-r--r-- 1 justin justin 824M Jan  7 15:21 words
  justin@box:~$ wc -l words
  144000000 words


  justin@box:~$ time (sort <words|uniq  -c)
  72000000 hello
  72000000 world

  real 0m22.831s
  user 0m32.999s
  sys 0m4.675s

Compared to doing it in memory with awk:

  justin@box:~$ time awk '{words[$1]++} END {for (w in words) printf("%s %d\n", w, words[w])}' < words
  hello 72000000
  world 72000000

  real 0m10.639s
  user 0m9.736s
  sys 0m0.876s

so, half the time and 1/3 the cpu.

View on HN

This is because in the first example you are invoking two programs. The first one sort the content of the file, the second count how many lines are equal.

While in the awk example it is creating a hash table with all words and incrementing by the key and then printing.

There is no sorting plus printing may be buffered.

Thanks for explaining my own comment to me.

Not explaining, trying to tell that you are comparing apples to oranges and making a conclusion based on that.

Also, you don't need to spawn a subshell nor feed sort via stdin in the first example :)

He's comparing apples to oranges and reaching the conclusion that... yes, apples and oranges are different things. He's quite aware of this, and even points out the tradeoff -- `sort | uniq -c` still works if your dataset doesn't fit into RAM.

Counting "words" vs sorting+counting "lines" are a complete different thing.

Heck, forget about RAM, the output of both programs don't even match.

That awk is pretty efficient and fast is no surprise ;)

All of your examples work in memory.

Not exactly. sort (at least GNU sort) will end up doing external merge sort on temporary files if you give it more data than you have memory. Which, if you give it 100GB of 5 different strings, ends up being a huge waste.

Not only GNU sort, but also postgresql, mysql and many more...

Please, "huge waste"? How do you sort something that does not fit in memory?

Are you being difficult on purpose?

I posted a comment on how 'sort | uniq -c | sort -n' is an interesting and very capable pipeline, but often misused and slower than other alternatives.

> you are comparing

Yes, I am comparing two methods of accomplishing the same thing. That is how comparing things works.

> Please, "huge waste"? How do you sort something that does not fit in memory?

Note how the full sentence included "if you give it 100GB of 5 different strings". If your input is 100GB of 5 different strings, then the hash table will easily fit in memory, and sorting the entire data set only to pass it to 'uniq -c' is indeed a 'huge waste'.

There are tons of large data sets that only have a small number of unique values in particular fields. protocols, ports, http status codes, hour of the day, etc. 'sort | uniq -c | sort -n' will work for all of them, but not nearly as efficient a hash table.

> Are you being difficult on purpose?

Programming is about paying the bare minimum attention to the details.

> [...] two methods of accomplishing the same thing [...]

Absolutelly not.

one prints:

  72000000 hello
  72000000 world

the other

  hello 72000000
  world 72000000

Now try both examples against a file with more than one column to understand what I'm talking about ;)

Even working in memory, there are different efficiencies for different methods.

Awk includes an asort() function which can sort an array, such that it would be possible to create a similar process entirely within awk to the sort | uniq -c pipeline:

    #!/usr/bin/gawk -f
    { x[NR] = $1 }
    END {
        rc = asort(x)
        j=0
        for(i in x) {
            if( x[i] "" == x[i-1] "" ) freq[j]++
     else {
         j++
         elem[j] = x[i]
         freq[j] = 1
     }
        }
        for(j in elem) {
            printf( "%6i %s\n", freq[j], elem[j])
        }
    }

As compares with a hash-based counter:

    #!/usr/bin/gawk -f
    { x[$1]++ }
    END { for(i in x ) printf( "%6i %s\n", x[i], i ) }

On a 2,000 value test dataset with 10 unique values:

sort | uniq -c takes 0.019s (8 runs averaged)

awk hash takes 0.023s (8 runs averaged)

awk-implemented sort + unique takes 0.33s (8 runs averaged)

In this case, sort | uniq is the fastest option. But the all-in-memory sort + separate tabulation of unique values in awk is notably slower (running in 143% of the time) than the also all-in-memory hash accumulator.

As I bump up the dataset size (20,000 records) that discrepency increases, roughly 0.052s sort|uniq, 0.065s hash, and 0.217s ask sort-unique.

TL;DR: test your assumptions, especially regarding performance.

Note: Data were generated with a simple bash loop:

    for i in {1..2000}; do echo $((RANDOM%10)); done  > data

With super small dataset sizes like that it'll fit in the L2 cache and can behave differently. I did test this though, and for 20,000 items generated with your loop:

sort | uniq -c takes .017s (fastest out of a few runs)

the awk command I used above takes .013s

A trivial implementation I have in go takes .08s

Additionally, using this 'protos' file which is 1,000,000 lines of tcp,udp,icmp:

  $ time (sort protos|uniq -c)
     5915 icmp
   332003 tcp
   662082 udp

  real 0m0.232s
  user 0m0.739s
  sys 0m0.100s

  $ # fixed to count 'lines' and not the first column, which makes it faster.
  $ time awk '{lines[$0]++} END {for (l in lines) printf("%s %d\n", l, lines[l])}'  < protos
  icmp 5915
  udp 662082
  tcp 332003

  real 0m0.194s
  user 0m0.190s
  sys 0m0.004s

  $ time ./c < protos
  662082 udp
  332003 tcp
  5915 icmp

  real 0m0.088s
  user 0m0.084s
  sys 0m0.005s

so yes, I do test my assumptions.

I was suggesting @crystaldev may not have.

And, more significantly, and as you've confirmed, not all in-memory processing is equivalent. There are faster and slower all-in-memory algorithms and implementations

Hrm... Maybe a bogounique implementation might be appropriate here....

(By analogy to bogosort: https://en.wikipedia.org/wiki/Bogosort)

Reply on news.ycombinator.com