Was 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.
After 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
I'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.
>If IO is a bottleneck it would be much worse while trying to swap around text lines in a giant memory mapped file.
There's no swapping of lines in a giant memory mapped file, the byte array of the file remains intact.
The program only swaps the line markers.
> Just convert the date to 64 or 32 bit integer
This would require extra memory for each line, complicate user interface (data formats vary a lot) and make the utility less generic, since you don't always want to sort chronologically. The current idea is to sort using as little extra memory as possible. This is because when files are already so big fitting them into RAM is a challenge already.
---
Finally, there's no evidence why the proposed solution would be faster. Empirically I have found that sorting chunks and merging is considerably slower than sorting in memory, which makes sense given how much faster RAM is than HDD.
> Just convert the date to 64 or 32 bit integer (or even less depending on the granularity and range of the dates).
We use rfc3339 because there's a lot of gotchas that appear when you conflate civil timekeeping with an absolute time scale. The number of seconds in a day is not constant, and generally only known a few months ahead of a coming leap second. Civil timekeeping syntaxes can deal with this gracefully exactly because they're a structured representation rather than absolute nanos relative to some epoch.
>- Saving the start and end position of a string that represents a date with 16 bytes is silly.
I am not saving the start and end positions of a string that represents a data; I am saving start and end position of a line, since I need to split the loaded file into lines. This requires extra memory. I tried sorting without caching the end position of the line (and always reading from start till \n), but it was slower to sort this way.
One 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
Thanks 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.
Indeed 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.
[+] [-] antender|5 years ago|reply
[+] [-] antender|5 years ago|reply
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] BubRoss|5 years ago|reply
- 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.
[+] [-] afiodorov|5 years ago|reply
There's no swapping of lines in a giant memory mapped file, the byte array of the file remains intact.
The program only swaps the line markers.
> Just convert the date to 64 or 32 bit integer
This would require extra memory for each line, complicate user interface (data formats vary a lot) and make the utility less generic, since you don't always want to sort chronologically. The current idea is to sort using as little extra memory as possible. This is because when files are already so big fitting them into RAM is a challenge already.
---
Finally, there's no evidence why the proposed solution would be faster. Empirically I have found that sorting chunks and merging is considerably slower than sorting in memory, which makes sense given how much faster RAM is than HDD.
[+] [-] jasonwatkinspdx|5 years ago|reply
We use rfc3339 because there's a lot of gotchas that appear when you conflate civil timekeeping with an absolute time scale. The number of seconds in a day is not constant, and generally only known a few months ahead of a coming leap second. Civil timekeeping syntaxes can deal with this gracefully exactly because they're a structured representation rather than absolute nanos relative to some epoch.
[+] [-] afiodorov|5 years ago|reply
I am not saving the start and end positions of a string that represents a data; I am saving start and end position of a line, since I need to split the loaded file into lines. This requires extra memory. I tried sorting without caching the end position of the line (and always reading from start till \n), but it was slower to sort this way.
[+] [-] jrockway|5 years ago|reply
[+] [-] easytiger|5 years ago|reply
[+] [-] TheTank|5 years ago|reply
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.
[+] [-] tleb_|5 years ago|reply
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] afiodorov|5 years ago|reply
[+] [-] jepcommenter|5 years ago|reply
$ 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|5 years ago|reply
[+] [-] afiodorov|5 years ago|reply
Edit: it finished!
real 35m28.370s
user 40m17.129s
sys 4m31.081s
[+] [-] loeg|5 years ago|reply
[+] [-] known|5 years ago|reply
[+] [-] afiodorov|5 years ago|reply
[+] [-] helltone|5 years ago|reply
gzip input.csv -c | wc -c
versus
cat input | wc -l
?