11 ms·
Show HN: Radix sort big files in memory
- TheTank 6y agoThanks for sharing. Do I understand correctly that this requires loading the whole file in memory along with an ordered list of keys? Or is it just the first n bytes that are loaded in memory? If the former, then it seems very expensive in terms of RAM, particularly if your data file has multiple columns. As an alternative I used is to load the file in a database, then sort by the key I want (which only loads the key in memory) and then output the result into a file. It does go through disk but you can address larger files as you only need the key in memory, and not the whole file.
- deleted 6y ago[deleted]
- tleb_ 6y agoIt does a memory map (mmap). Your file is addressed in virtual memory. See https://en.wikipedia.org/wiki/Mmap https://en.wikipedia.org/wiki/Mmap and https://en.wikipedia.org/wiki/Memory-mapped_file https://en.wikipedia.org/wiki/Memory-mapped_file
- afiodorov 6y agoIndeed I load the entire file, but I think provided I have RAM to load the file with all the columns, the approach of loading everything should give me optimal performance. However I agree with your approach when there isn't enough RAM.
- BubRoss 6y agoI'm not sure what the point of this is, it is something basic but implemented poorly. - Saving the start and end position of a string that represents a date with 16 bytes is silly. Just convert the date to 64 or 32 bit integer (or even less depending on the granularity and range of the dates). - run through the file converting the dates to a smaller integer representation. When the array of integers is too big, sort it and use that to write a sorted text file chunk - once that is done, merge the text file chunks together Any good sorting algorithm is going to be able to do this in under 20 minutes with 16 cores. If IO is a bottleneck it would be much worse while trying to swap around text lines in a giant memory mapped file.
- jrockway 6y agoI guess what surprises me about this is how bad "sort" did.
- BubRoss 6y agoIts use case is usually going to be sorting the output of other commands, I'm impressed it works at all. If you want to test something meant to scale, feed everything into an sqlite database and read it back. Sqlite should chew through this without any problem.
- fwip 6y agoA similar approach was used in this tool, whose writeup I found quite interesting: https://devblog.dnanexus.com/faster-bam-sorting-with-samtools-and-rocksdb/ https://devblog.dnanexus.com/faster-bam-sorting-with-samtool... Background: "samtools," a tool meant for processing multi-gigabyte genomic alignment data, uses a sort algorithm basically the same as `sort`. This fork instead jams the data into Facebook's RocksDB, and then extracts it back out. Speedup ranged from 1.2x to 5x, with bigger input files and slower disks seeing the most gains.
- easytiger 6y agoOne doesn't always control the input format of data one receives. Indeed a lot of stuff I've cobbled together in real work is munging many and varied logs
- known 6y agoWhat would be the result when we add these sort options sort -f -s --batch-size=1024 -T/home
- afiodorov 6y agoCould you elaborate more why this could be faster? These experiments take some time to complete. Also should I not use --parallel flag?
- known 6y agoSorry I meant to tune sort LC_ALL=C sort --parallel=16 -t, -k1 -S100% -f -s --batch-size=1024 -T/home /tmp/test
- afiodorov 6y agoI had to reduce the batch-size to 512, because otherwise sort complained with batch-size too large. The timings are: real 30m54.557s user 82m9.055s sys 3m1.723s no improvement over sort without the batch-size...
- jepcommenter 6y agoAs you sort by first field anyway, could you please try out omitting field split (-t, -k1)? For me it gives a noticeable improvement: $ stat --printf="%s\n" p.csv 1258291200 $ time sort -t, -k1 -S100% -o sorted.csv p.csv real 0m50,186s user 4m6,962s sys 0m4,562s $ time sort -o sorted.csv p.csv real 0m43,483s user 3m36,473s sys 0m4,282s
- jepcommenter 6y agoFull line comparison would probably use memcmp that bails out on first non matching character while field-splitting overhead might be significant.
- afiodorov 6y agoExact same file has been taking more than 35 minutes to sort already, so it's slower without splitting. Edit: it finished! real 35m28.370s user 40m17.129s sys 4m31.081s
- loeg 6y agoWhere did you find the dataset, or did you construct your own?
- afiodorov 6y agoIt's a dataset related to balance changes of bitcoin addresses downsampled to daily resolution. You could extract it from BigQuery's bitcoin public data.
- antender 6y agoWas there any external requirement to specifically sort this file in-memory only? Why not just split the file into chunks (around 100MB), sort them as usual, and then k-way merge sort them after that. This, in theory, can be faster than allocating lots of RAM for radix tree, especially if you use SSD instead of HDD.
- antender 6y agoAfter consulting with GNU sort manual: sort has -m option just for the case of merging presorted files, so you can test this by using 'split -l', then 'xargs sort' (to parallelize), then 'sort -m' to merge chunks
- afiodorov 6y agoI agree that a significant proportion of time is spent on IO. Only 8m38s is actually spent sorting (out of 19m37s). However in the past my experiments have shown that using `sort -m` to sort chunks is much much slower than using `sort -S100%`.
- deleted 6y ago[deleted]
- helltone 6y agoOut of curiosity, what is the entropy of your input? ie what's the output of gzip input.csv -c | wc -c versus cat input | wc -l ?