5

My file has millions of lines, resides in memory /dev/shm/tmp.file, is accessed by multiple threads, looks like this

831092,25a1bd66f2eec71aa2f0a8bb3d,/path/to/a/file
4324,8d83c29e4d8c71bd66f1bd66fs,/path/to/another/file
...

and is sorted by the part after the second , with sort -t , -k3. In general each line has the shape [0-9]*,[0-9a-z]*,.* and file paths can contain any characters except \0 or \n.

I need to extract the lines of all files that reside within a given directory as quickly as possible and without making an additional copy. Since the file is sorted that way, the lines I am looking for are an uninterrupted chunk of the file.

Currently I use grep -F ',<directory>' /dev/shm/tmp.file but I know it would be much quicker to do a binary search for the first hit and then expand the chunk line by line or with another binary search without reading in the entire file for each new line. However, this has to be integrated into a bash script, and I found no way to do something like lseek in the bash.

There is sgrep but it requires the complete lines to be sorted.

How can I extract all matches with ',<directory>' quicker than grep -F?

Edit: The input /dev/shm/tmp.file is only there to do this kind of extraction. Hence, pre-processing it in some way to make the job easier is an option.

Edit: a.b sorting between a and a/b is not an issue since all subdirectories should be included in the chunk.

  • 1
    If this was something I did and wanted to be able to do efficiently and often, I would probably put it into a database and index the paths by directory inode and mountpoint, or something. – Kusalananda Feb 7 at 16:30
  • This is well beyond the limits of bash. You could do it a little faster using awk, as you could make awk stop once it had found the end of the block of lines. However it would still search in order. – Philip Couling Feb 7 at 16:51
  • 1
    Are those records NUL-delimited? If not then I'd expect newline to be another character that can't be found in your file names. You'll also want to make sure that sort -t , -k3 is done in the C locale. Even in the C locale, note that a.b sorts inbetween a and a/b. – Stéphane Chazelas Feb 7 at 16:56
  • zsh and ksh93 have builtin seeking operator, but even there, you wouldn't want to implement that with shell builtins. mmapping it would probably make more sense than seeking here anyway. – Stéphane Chazelas Feb 7 at 17:00
  • @StéphaneChazelas You are right \n can also be excluded. How would I do the mapping? – katosh Feb 7 at 17:02
8

If you changed 831092,25a1bd66f2eec71aa2f0a8bb3d,/path/to/a/file to /path/to/a/file,831092,25a1bd66f2eec71aa2f0a8bb3d

You could do it with:

look /path/to/ /dev/shm/tmp.file

look is a traditional Unix utility from the 70s, not specified by POSIX but fairly common. On Debian and derivatives, you'll find one in the bsdmainutils package, there's also one in util-linux (also copied from BSD, not on the Debian package by the same name).

look mmap()s the file and does a binary search.

However note that the Debian implementation reverts to a basic linear search a la grep unless you pass the -b option (sigh). So, on Debian or derivative, you'll want:

look -b /path/to/ /dev/shm/tmp.file

Also note that some implementations have a limit on the size of the file they can handle (see corresponding bug with patch for Debian's)

  • This is neat, thanks. A downside is that I will have to change the format back again before passing on the chunks. – katosh Feb 7 at 17:19
  • The file size is an issue as look reports look: /dev/shm/tmp.file: File too large. I am not sure I can get this to work on different Debian/Ubuntu machines. Will look into it tomorrow. – katosh Feb 7 at 18:09
  • The sorting of the proposed format for look does not always agree with the sorting by file paths. E.g., if there are files a and a,5 in a directory, then sorting for look would probably put a before or after a,5 depending on the number coming after the file name. Also look occasionally complains look: Invalid or incomplete multibyte or wide character. Other than that it's a brilliant solution that works flawlessly with Tomaž Šolcs patch. The other patch, however, seems to break look for regular files. – katosh Feb 8 at 12:30
  • 1
    @katosh, you'll want to use LC_ALL=C for both sort and look. The order is generally not deterministic in other locales (and is much more complex and expensive) – Stéphane Chazelas Feb 8 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.