4 ms·

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 wi

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.

jrockway 6y ago
I guess what surprises me about this is how bad "sort" did.
- BubRoss 6y ago
  Its 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 ago
    A 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 ago
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
- BubRoss 6y ago
  This post talks about a specific type of input that the sort command takes.
  - easytiger 6y ago
    Yea, it's used as the default DT format on tons of logging libraries.
    - BubRoss 6y ago
      I'm lost on exactly what you are trying to say here. Something that can be radix sorted can likely be condensed at least partially to an integer.
jasonwatkinspdx 6y ago
> 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.
- BubRoss 6y ago
  They only need to be converted one way so that sorting is fast. You might be overthinking this.
afiodorov 6y ago
>- 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.
- BubRoss 6y ago
  Why save the start and end? Why not just save the barrier between each line?
  - afiodorov 6y ago
    as I mentioned in the parent comment I tried saving just the start of each line, and then during sorting scan from the start until '\n' character, but this turned out to be much slower
    - BubRoss 6y ago
      If you save the break between each line, you wouldn't have to scan to the end of the line, you would just look at the next line break.
      - afiodorov 6y ago
        this would work, but once I start sorting lines I'll need a copy of original line breaks array; so in the end I'd need 16 bytes per line anyway
afiodorov 6y ago
>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.

jrockway 6y ago

I guess what surprises me about this is how bad "sort" did.

BubRoss 6y ago
Its 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 ago
  A 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 ago

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

BubRoss 6y ago
This post talks about a specific type of input that the sort command takes.
- easytiger 6y ago
  Yea, it's used as the default DT format on tons of logging libraries.
  - BubRoss 6y ago
    I'm lost on exactly what you are trying to say here. Something that can be radix sorted can likely be condensed at least partially to an integer.

jasonwatkinspdx 6y ago

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

BubRoss 6y ago
They only need to be converted one way so that sorting is fast. You might be overthinking this.

afiodorov 6y ago

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

BubRoss 6y ago
Why save the start and end? Why not just save the barrier between each line?
- afiodorov 6y ago
  as I mentioned in the parent comment I tried saving just the start of each line, and then during sorting scan from the start until '\n' character, but this turned out to be much slower
  - BubRoss 6y ago
    If you save the break between each line, you wouldn't have to scan to the end of the line, you would just look at the next line break.
    - afiodorov 6y ago
      this would work, but once I start sorting lines I'll need a copy of original line breaks array; so in the end I'd need 16 bytes per line anyway

afiodorov 6y ago

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