3 ms·

Perhaps an indication of how much time tgrep currently spends looking in a sample 70GB file would be of interest.

by kgtm 16y ago

jemfinch 16y ago
Is it really that hard to figure out? Imagine an implementation that does a binary search through the characters of a file; when it lands in the middle of the line, it seeks back by one character until it finds the beginning of the line, and then compares that line to the timestamp given. 70GB will require approximately 36 binary searches to find the line you want. Assuming the lines are around 200 characters long, each binary search will require on average 100 seeks backward to find the beginning of the line. From there you can read the characters you need for the timestamp. So your total cost is going to be 36 * (1 seek to the character, 100 seeks to the beginning of the line, a read from that offset), disregarding the almost certainly irrelevant cost of comparison to the timestamp. Note that these seeks, while still calls to seek(2), are not actual random disk seeks, because disks return blocks to the OS in 16KB chunks or so. Most of those seeks will just be a quick roundtrip through the kernel. So you'll do, on average, 36 reads and 3636 seeks. On most modern computers, that will take maybe 100ms, which agrees with my experience in writing a similar program for some of the logfiles I work with.
- kgtm 16y ago
  The number of upvotes you get should be a good indication of the difficulty, perceived or otherwise.
- e-dard 16y ago
  You're ignoring real-world aspects of the problem. For example, you're assuming that the data points are evenly distributed across time. Reddit will most likely have regular busy and quiet periods, which will impact the density of the log at certain times. Thus, one can tune the algorithm to work better on Reddit's specific visitor pattern, if you can learn it. As an example, you need to jump back further in the file to get from 8pm to 6pm than you do to jump back from 4am to 2am. <- assuming US time, which they don't.
  - jemfinch 16y ago
    > You're ignoring real-world aspects of the problem. No, I'm not. The most important real world aspect of this problem is that I can pull the complex part, the binary search, off the standard library shelf. All I need to implement is a random access iterator over the lines of an open file and I'm set. > For example, you're assuming that the data points are evenly distributed across time No, I'm not. I just don't care how they're distributed across times. 70GB is between 2^36 and 2^37 bytes. It's probably around 2^28 or 2^29 lines. Binary search over the characters would take at most 37 probes; over the lines it would take at most 29 probes. Since each probe is so cheap (one disk seek and one disk read, essentially) there's absolutely no reason to optimize any further, especially when I can use an off-the-shelf component like C++'s std::lower_bound to do my binary search for me. > Reddit will most likely have regular busy and quiet periods, which will impact the density of the log at certain time If you think that impacts the runtime of binary search at all, you've got a serious misconception about how binary search works. > Thus, one can tune the algorithm to work better on Reddit's specific visitor pattern, if you can learn it. Why bother? We're talking about a savings of milliseconds on an interactive process. An ordinary human like myself would never even notice the difference. The network lag from SSH alone would be greater than the difference in runtime.
    - tjsnyder 16y ago
      This is absolutely correct. The worst case in any binary search is exactly floor(lg n + 1) where the element doesn't exist. There is no reason to optimize any further than this.
      - jemfinch 16y ago
        To be clear, interpolation search can cut down the runtime by another log factor (`O(log log n)` instead of `O(log n)`) but it's just not worth the effort, especially in this case, precisely because the lines aren't uniformly distributed.
        e-dard 16y ago

Perhaps an indication of how much time tgrep currently spends looking in a sample 70GB file would be of interest.

by kgtm 16y ago

Perhaps an indication of how much time tgrep currently spends looking in a sample 70GB file would be of interest.

Is it really that hard to figure out? Imagine an implementation that does a binary search through the characters of a file; when it lands in the middle of the line, it seeks back by one character until it finds the beginning of the line, and then compares that line to the timestamp given. 70GB will require approximately 36 binary searches to find the line you want. Assuming the lines are around 200 characters long, each binary search will require on average 100 seeks backward to find the beginning of the line. From there you can read the characters you need for the timestamp. So your total cost is going to be 36 * (1 seek to the character, 100 seeks to the beginning of the line, a read from that offset), disregarding the almost certainly irrelevant cost of comparison to the timestamp. Note that these seeks, while still calls to seek(2), are not actual random disk seeks, because disks return blocks to the OS in 16KB chunks or so. Most of those seeks will just be a quick roundtrip through the kernel. So you'll do, on average, 36 reads and 3636 seeks. On most modern computers, that will take maybe 100ms, which agrees with my experience in writing a similar program for some of the logfiles I work with.

kgtm 16y ago
The number of upvotes you get should be a good indication of the difficulty, perceived or otherwise.
e-dard 16y ago
You're ignoring real-world aspects of the problem. For example, you're assuming that the data points are evenly distributed across time. Reddit will most likely have regular busy and quiet periods, which will impact the density of the log at certain times. Thus, one can tune the algorithm to work better on Reddit's specific visitor pattern, if you can learn it. As an example, you need to jump back further in the file to get from 8pm to 6pm than you do to jump back from 4am to 2am. <- assuming US time, which they don't.
- jemfinch 16y ago
  > You're ignoring real-world aspects of the problem. No, I'm not. The most important real world aspect of this problem is that I can pull the complex part, the binary search, off the standard library shelf. All I need to implement is a random access iterator over the lines of an open file and I'm set. > For example, you're assuming that the data points are evenly distributed across time No, I'm not. I just don't care how they're distributed across times. 70GB is between 2^36 and 2^37 bytes. It's probably around 2^28 or 2^29 lines. Binary search over the characters would take at most 37 probes; over the lines it would take at most 29 probes. Since each probe is so cheap (one disk seek and one disk read, essentially) there's absolutely no reason to optimize any further, especially when I can use an off-the-shelf component like C++'s std::lower_bound to do my binary search for me. > Reddit will most likely have regular busy and quiet periods, which will impact the density of the log at certain time If you think that impacts the runtime of binary search at all, you've got a serious misconception about how binary search works. > Thus, one can tune the algorithm to work better on Reddit's specific visitor pattern, if you can learn it. Why bother? We're talking about a savings of milliseconds on an interactive process. An ordinary human like myself would never even notice the difference. The network lag from SSH alone would be greater than the difference in runtime.
  - tjsnyder 16y ago
    This is absolutely correct. The worst case in any binary search is exactly floor(lg n + 1) where the element doesn't exist. There is no reason to optimize any further than this.
    - jemfinch 16y ago
      To be clear, interpolation search can cut down the runtime by another log factor (`O(log log n)` instead of `O(log n)`) but it's just not worth the effort, especially in this case, precisely because the lines aren't uniformly distributed.
      - e-dard 16y ago