Who killed my sort? or How to efficient count distinct values from a csv column

Question

I'm doing some processing trying to get how many different lines in a file containing 160,353,104 lines. Here is my pipeline and stderr output.

$ tail -n+2 2022_place_canvas_history.csv | cut -d, -f2 | tqdm --total=160353104 |\
  sort -T. -S1G | tqdm --total=160353104 | uniq -c | sort -hr > users

100%|████████████████████████████| 160353104/160353104 [0:15:00<00:00, 178051.54it/s]
 79%|██████████████████████      | 126822838/160353104 [1:16:28<20:13, 027636.40it/s]

zsh: done tail -n+2 2022_place_canvas_history.csv | cut -d, -f2 | tqdm --total=160353104 | 
zsh: killed sort -T. -S1G | 
zsh: done tqdm --total=160353104 | uniq -c | sort -hr > users

My command-line PS1 or PS2 printed the return codes of all process of the pipeline. ✔ 0|0|0|KILL|0|0|0 First char is a green checkmark that means that last process returned 0 (success). Other numbers are return code for each one of pipelined processes, in same order. So I've notice that my fourth command got KILL status, this is my sort command sort -T. -S1G setting local directory to temp storage and buffer up to 1GiB.

The question is, why did it returned KILL, does it means something sent a KILL SIGN to it? Is there a way to know "who killed" it?

Updates

After reading Marcus Müller Answer, first I've tried to load the data into Sqlite.

So, maybe this is a good moment to tell you that, no, don't use a CSV-based data flow. A simple

sqlite3 place.sqlite

and in that shell (assuming your CSV has a title row that SQLite can use to determine the columns) (of course, replace $second_column_name with the name of that column)

.import 022_place_canvas_history.csv canvas_history --csv
SELECT $second_column_name, count($second_column_name)   FROM canvas_history 
GROUP BY $second_column_name;

This was taking a lot of time, so I leave it processing and went to do other things. While it I thought more about this other paragraph from Marcus Müller Answer:

You just want to know how often each value appeared on the second column. Sorting that before just happens because your tool (uniq -c) is bad, and needs the rows to be sorted before (there's literally no good reason for that. It's just not implemented that it could hold a map of values and their frequency and increase that as they appear).

So I thought, I can implement that. When I got back into computer, my Sqlite import process had stopped cause of a SSH Broken Pip, think as it didn't transmit data for a long time it closed the connection. Ok, what a good opportunity to implement a counter using a dict/map/hashtable. So I've write the follow distinct file:

#!/usr/bin/env python3
import sys

conter = dict()

# Create a key for each distinct line and increment according it shows up. 
for l in sys.stdin:
    conter[l] = conter.setdefault(l, 0) + 1 # After Update2 note: don't do this, do just `couter[l] = conter.get(l, 0) + 1`

# Print entries sorting by tuple second item ( value ), in reverse order
for e in sorted(conter.items(), key=lambda i: i[1], reverse=True):
    k, v = e
    print(f'{v}\t{k}')

So I've used it by the follow command pipeline.

tail -n+1 2022_place_canvas_history.csv | cut -d, -f2 | tqdm --total=160353104 | ./distinct > users2

It was going really really fast, projection of tqdm to less than 30 minutes, but when got into 99% it was getting slower and slower. This process was using a lot of RAM, about 1.7GIB. Machine I'm working with this data, the machine I have storage enought, is a VPS with just 2GiB RAM and ~1TiB storage. Thought it may be getting so slow cause SO was having to handle these huge memory, maybe doing some swap or other things. I've waited anyways, when it finally got into 100% in tqdm, all data was sent into ./distinct process, after some seconds got the follow output:

160353105it [30:21, 88056.97it/s]                                                                                            
zsh: done       tail -n+1 2022_place_canvas_history.csv | cut -d, -f2 | tqdm --total=160353104 | 
zsh: killed     ./distinct > users2

This time mostly sure cause by out-of-memory-killer as spotted in Marcus Müller Answer TLDR section.

So I've just checked and I don't have swap enabled in this machine. Disabled it after complete its setup with dmcrypt and LVM as you may get more information in this answers of mine.

So what I'm thinking is to enable my LVM swap partition and trying to run it again. Also at some moment I think that I've seen tqdm using 10GiB of RAM. But I'm pretty sure I've seen wrongly or btop output mixed up, as latter it showed only 10MiB, don't think tqdm would use much memory as it just counts and updates some statics when reading a new \n.

In Stéphane Chazelas comment to this question they say:

The system logs will possibly tell you.

I would like to know more about it, should I find something in journalctl? If so, how to do it?

Anyways, as Marcus Müller Answer says, loading the csv into Sqlite may be by far the most smart solution, as it will allow to operate on data in may ways and probably has some smart way to import this data without out-of-memory.

But now I'm twice curious about how to find out why as process was killed, as I want to know about my sort -T. -S1G and now about my ./distinct, the last one almost sure it was about memory. So how to check for logs that says why those process were killed?

Update2

So I've enabled my SWAP partition and took Marcus Müller suggestion from this question comment. Using pythons collections.Counter. So my new code (distinct2) looks like this:

#!/usr/bin/env python3
from collections import Counter
import sys

print(Counter(sys.stdin).most_common())

So I've run Gnu Screen to even if I get a broken pipe again I could just resume the session, than run it in the follow pipeline:

tail -n+1 2022_place_canvas_history.csv | cut -d, -f2 | tqdm --total=160353104 --unit-scale=1 | ./distinct2 | tqdm --unit-scale=1 > users5

That got me the follow output:

160Mit [1:07:24, 39.6kit/s]
1.00it [7:08:56, 25.7ks/it]

As you can see it took way more time to sort the data than to count it. One other thing you may notice is that tqdm second line output shows just 1.00it, it means it got just a single line. So I've checked the user5 file using head:

head -c 150 users5 
[('kgZoJz//JpfXgowLxOhcQlFYOCm8m6upa6Rpltcc63K6Cz0vEWJF/RYmlsaXsIQEbXrwz+Il3BkD8XZVx7YMLQ==\n', 795), ('JMlte6XKe+nnFvxcjT0hHDYYNgiDXZVOkhr6KT60EtJAGa

As you can see, it printed the entire list of tuples in a single line. For solving this I've used the good old sed as follow sed 's/),/)\n/g' users5 > users6. After it I've checked users6 content using head, as follow with its output:

$ head users6
[('kgZoJz/...c63K6Cz0vEWJF/RYmlsaXsIQEbXrwz+Il3BkD8XZVx7YMLQ==\n', 795)
 ('JMlte6X...0EtJAGaezxc4e/eah6JzTReWNdTH4fLueQ20A4drmfqbqsw==\n', 781)
 ('LNbGhj4...apR9YeabE3sAd3Rz1MbLFT5k14j0+grrVgqYO1/6BA/jBfQ==\n', 777)
 ('K54RRTU...NlENRfUyJTPJKBC47N/s2eh4iNdAKMKxa3gvL2XFqCc9AqQ==\n', 767)
 ('8USqGo1...1QSbQHE5GFdC2mIK/pMEC/qF1FQH912SDim3ptEFkYPrYMQ==\n', 767)
 ('DspItMb...abcd8Z1nYWWzGaFSj7UtRC0W75P7JfJ3W+4ne36EiBuo2YQ==\n', 766)
 ('6QK00ig...abcfLKMUNur4cedRmY9wX4vL6bBoV/JW/Gn6TRRZAJimeLw==\n', 765)
 ('VenbgVz...khkTwy/w5C6jodImdPn6bM8izTHI66HK17D4Bom33ZrwuGQ==\n', 758)
 ('jjtKU98...Ias+PeaHE9vWC4g7p2KJKLBdjKvo+699EgRouCbeFjWsjKA==\n', 730)
 ('VHg2OiSk...3c3cr2K8+0RW4ILyT1Bmot0bU3bOJyHRPW/w60Y5so4F1g==\n', 713)

Good enough to work latter. Now I think I should add an update after trying to check who killed my sort using dmesg ou journalctl. I'm also wondering if there is a way to make this script faster. Maybe creating a threadpool, but have to check pythons dict behavior, also thought about other data-structures as the column I'm counting is fixed width string, maybe using a list to storage the frequency of each different user_hash. Also I read the python implementation of Counter, it's just a dict, pretty much same implementation I had before, but instead of using dict.setdefault just used dict[key] = dict.get(key, 0) + 1, it was a miss-usage of setdefault no real need for this scenario.

Update3

So I'm getting so deep in the rabbit hole, totally lost focus of my objective. I started search for faster sorting, maybe write some C or Rust, but realized that already have the data I came for processed. So I'm here to show dmesg output and one final tip about the python script. The tip is: may be better to just count using dict or Counter, than sort its output using gnu sort tool. Probably sort sorts faster than python sorted buitin function.

About dmesg, it was pretty simple to find out of memory, just did a sudo dmesg | less press G to go all way down, than ? to search back, than searched for Out string. Found two of them, one for my python script and another to my sort, the one that started this question. Here is those outputs:

[1306799.058724] Out of memory: Killed process 1611241 (sort) total-vm:1131024kB, anon-rss:1049016kB, file-rss:0kB, shmem-rss:0kB, UID:1000 pgtables:2120kB oom_score_adj:0
[1306799.126218] oom_reaper: reaped process 1611241 (sort), now anon-rss:0kB, file-rss:0kB, shmem-rss:0kB
[1365682.908896] Out of memory: Killed process 1611945 (python3) total-vm:1965788kB, anon-rss:1859264kB, file-rss:0kB, shmem-rss:0kB, UID:1000 pgtables:3748kB oom_score_adj:0
[1365683.113366] oom_reaper: reaped process 1611945 (python3), now anon-rss:0kB, file-rss:0kB, shmem-rss:0kB

That's it, thank you so much for helping so far, hope it help others too.

Answer 1

TL;DR: out-of-memory-killer or running out of disk space for temporary files kills sort. Recommendation: Use a different tool.

---

I've had a glance over GNU coreutils' sort.c right now¹. Your -S 1G just means that the sort process tries to allocate memory in a chunk of 1GB, and will fall back to increasingly smaller sizes if that is not possible.

After having exhausted that buffer, it will create a temporary file to store the already sorted lines², and sort the next chunk of input in-memory.

After all input has been consumed, sort will then merge/sort two of the temporary file into a temporary file (mergesort-style), and successively merge all the temporaries until the merging will yield the total sorted output, which is then output to stdout.

That's clever, because it means you can sort input larger than available memory.

Or, it's clever on systems where these temporary files are not themselves held in RAM, which they typically are these days (/tmp/ is typically a tmpfs, which is a RAM-only file system). So, writing these temporary files eats exactly the RAM you're trying to save, and you're running out of RAM: your file has 160 million lines, and a quick google suggests it's 11GB of uncompressed data.

You can "help" sort around that by changing the temporary directory it uses. You're already doing that, -T., placing the temporary files in your current directory. Might be you're running out of space there? Or is that current directory on tmpfs or similar?

You've got a CSV file with an medium amount of data (160 million rows is not that much data for a modern PC). Instead of putting that into a system meant to deal with that much data, you're trying to operate on it with tools from the 1990s (yes, I just read sort git history), when 16 MB RAM seemed quite generous.

CSV is just the wrong data format for processing any significant amount of data, and your example is the perfect illustration of that. Inefficient tooling working on inefficient data structure (a text file with lines) in inefficient ways to achieve a goal with an inefficient approach:

You just want to know how often each value appeared on the second column. Sorting that before just happens because your tool (uniq -c) is bad, and needs the rows to be sorted before (there's literally no good reason for that. It's just not implemented that it could hold a map of values and their frequency and increase that as they appear).

---

So, maybe this is a good moment to tell you that, no, don't use a CSV-based data flow. A simple

sqlite3 place.sqlite

and in that shell (assuming your CSV has a title row that SQLite can use to determine the columns) (of course, replace $second_column_name with the name of that column)

.import 022_place_canvas_history.csv canvas_history --csv
SELECT $second_column_name, count($second_column_name)
  FROM canvas_history
  GROUP BY $second_column_name;

is likely to be as fast, and bonus, you get an actual database file place.sqlite. You can play around with that much more flexibly – for example, create a table where you extract coordinates, and convert the times to numerical timestamps, and then be much faster and more flexible by what you analyze.

---

¹ The globals, and the inconsistency on what is used when. They hurt. It was a different time for C authors. And it's definitely not bad C, just ... not what you're used to from more modern code bases. Thanks to Jim Meyering and Paul Eggert for writing and maintaining this code base!

² you can try to do the following: sort a file that's not too massive, say, ls.c with say has 5577 lines, and record the number of files opened:

strace -o /tmp/no-size.strace -e openat sort ls.c
strace -o /tmp/s1kB-size.strace -e openat sort -S 1 ls.c
strace -o /tmp/s100kB-size.strace -e openat sort -S 100 ls.c
wc -l /tmp/*-size.strace

Answer 2

The answer from @MarcusMüller is clear enough about "Who killed my sort?". And you have confirmed the issue.

However, the second part has not been addressed much: or How to efficient count distinct values from a csv column. Beside trying to find better/faster ways to sort.

That's because your pipes have (all) been based on using uniq. And uniq requires sorted data.

Is there any other solution?

Yes. Build an array with column 2 data as key and add 1 each time such value is found. That is the usual way in which awk processes data:

$ awk -F, '{count[$2]++}END{for (i in count) {print i,count[i]}}'

That doesn't need to retain the whole file in memory as sort does. But only the list of keys (like the 'kgZoJz//JpfXgowLxOhcQlFYOCm8m6upa6Rpltcc63K6Cz0vEWJF/RYmlsaXsIQEbXrwz+Il3BkD8XZVx7YMLQ==\n' you have shown and a float for the count).

That will process each line of the file once and in the order they appear, no sort required to count unique users. But yes, a final sort to get counts sorted is required.

So the time to process the file will be proportional to n instead of the time to sort n*log(n) and the memory use will be proportional to the number of users 'm' (second field uniq keys).

If the average count of each user is 350 (assuming that ~795 is the maximum, 1 is the minimum, and the count goes linearly between the two counts), then the size of memory used should be proportional to 88 (size of a key) times 160353104/350 (number of distinct keys), or less than 40 megabytes plus some overhead.