5 ms·

I'm surprised that they are storing Unicode characters instead of bytes. For example Rust's regex library works on bytes and unicode patterns are compiled into

I'm surprised that they are storing Unicode characters instead of bytes. For example Rust's regex library works on bytes and unicode patterns are compiled into byte patterns which means that it doesn't need to worry about unicode and variable length characters when matching. You'd think for code where the vast majority is ASCII this would be a huge improvement. I guess the downside is that searches for emoji and other "long" characters would need to look up more index entries. However I would expect that due to the rarity of that it would be beneficial overall.

Scaevolus 5y ago
The source code itself is stored as UTF-8, but the trigrams were represented as Unicode codepoints in the index. The last optimization packs the ASCII trigrams for efficiency.
- kevincox 5y ago
  But that's my point. Why not just store bytes, they you don't have to worry about packing, it is always packed. If I understand correctly they are using 8 bytes for 3 codepoints. They could instead use 3 bytes for 3 bytes. This would use significantly less memory and would rarely be less selective. (If that was a concern they could probably consider 4-grams instead of trigrams and still use less memory.) This also doesn't precude the splitting into the first 2 characters and last 1.
  - Scaevolus 5y ago
    Oh, certainly, you could change the architecture to have byte-trigrams. These optimizations work without any large-scale architecture changes, making them safer to test and deploy, no data migrations or reindexing required!
- roca 5y ago
  I think the real question is: why not use trigrams of bytes (from the UTF8 representation) instead of Unicode codepoints? Seems like that would simplify everything. If they have data showing that doesn't work as well in practice, I'd love to know what it is, because I can't think of a reason off the top of my head why it wouldn't work well. Obviously it could only be worse in non-ASCII situations, which are already super-rare.
  - bastawhiz 5y ago
    Because then you've potentially got a lot of trigrams for 4-byte Unicode characters that only contain the first three bytes of the character. Even if they're rare, you're effectively hamstringing anyone who uses a language that includes four byte characters or emoji. And for languages that use characters with three bytes, you're essentially indexing individual characters. Even in the case where you're using two byte characters, which is very common, your trigrams become one and a half characters. But moreover, the prefix of many of your trigrams is just going to be surrogate pair bytes. At this point, the whole point of building a reverse index is somewhat moot if you're indexing over parts of characters, byte sequences that are not useful on their own, and other such garbage. Yes, the ASCII happy path is fine, but you've essentially eliminated Unicode support entirely.
    - roca 5y ago
      > the prefix of many of your trigrams is just going to be surrogate pair bytes I'm not sure what you mean by this. Surrogate pairs are a UTF16 thing, not relevant here. > you've essentially eliminated Unicode support entirely. That's not obvious to me at all. In text containing non-ASCII characters, the trigrams that span UTF8 character boundaries are likely to give you the selectivity you need. > And for languages that use characters with three bytes, you're essentially indexing individual characters Not at all. The index would be a function of character pairs. It certainly could be worse but how much worse would depend on the characteristics of the source texts, which is why I think it would be really interesting to see whatever data Sourcegraph has on this.
      - bastawhiz 5y ago
        > Not at all. The index would be a function of character pairs. If it's a three byte trigram and it covers a three byte character, please explain how it could be anything other than a trigram containing a single character? If you want to cover a pair characters, you need six bytes. Which is also simply worse than the 42 bits you need to encode two Unicode code points as integers (as the author is doing now).
hanwenn 5y ago
Hi, Zoekt author here. There are a bunch of interesting replies, but they all miss the point. The reason you can't use bytes is a combination of two things: (1) code search supports case-insensitive matching. (2) the search algorithm uses distance between trigram occurrences to reduce the number of matches. With UTF-8, different case flavors of a character have different widths. For example, k (ascii k, 1 byte), K (ascii K, 1 byte) and K (unicode U+212A for Kelvin, 3 bytes). This messes up algorithm (2). The same consideration holds if you want to support searches where "a" also matches "á" and "ã". I did a talk on exactly this subject in 2017, which goes into more detail. The bit that explains it is here, https://youtu.be/_-KTAvgJYdI?t=602 https://youtu.be/_-KTAvgJYdI?t=602 . If you have more time, you can watch the entire thing, as it is entertaining, if I may say so :)
- Sesse__ 5y ago
  If you actually want to be UCA-compliant, though, it won't really help you to use codepoints. Different Unicode normalization, contractions and ignorables really mess up things. (In general, you can't search by case-folding if you want all the edge cases right; you have to apply the full Unicode collation algorithm.) I wonder if it's possible to store UCA weights instead of code points in the trigrams, but I haven't thought deeply about it, and it would surely affect indexing speed. In plocate, where I have this exact same issue, I solve it half-heartedly by using 3-byte trigrams and then constructing a whole bunch of alternatives, even if they differ in width. (I don't support accent-insensitive search and I don't support contractions, so locate ß won't find SS.) See https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp;h=678f520fd03cc7c11c63b3cae7f77e712196c56f;hb=HEAD#l197 https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp... — but it doesn't support the Kelvin case if it's in the filename and you give K on the command line.
- kevincox 5y ago
  > (1) code search supports case-insensitive matching. I'm not quite sure why this matters. Either you are case folding before you store and both cases are the same or you are expanding the query to consider all cases and both cases are the same. You are effectively storing "UTF-8" anyways. It is just whether you are storing 3 bytes or 3 characters. > (2) the search algorithm uses distance between trigram occurrences to reduce the number of matches. Could you not still measure this distance in codepoints? Or is there a benefit to tying this to the length of the trigrams? > The same consideration holds if you want to support searches where "a" also matches "á" and "ã". Well IIRC á can be two codepoints as well (if it isn't normalized) so don't you need to handle this case anyways?
benibela 5y ago
I use another regex library that does that and do not like it at all Something like \w makes the regex complexity explode. It spends more time building the regex than actually matching it.
- burntsushi 5y ago
  You can't get around the Unicode problem for free. If your state machine operates on codepoints, then your state machine is almost certainly very slow. Not only because you now need to do UTF-8 decoding, but you also probably need a sparse representation (e.g., a hash map) to deal with the large space of Unicode codepoints since that's what your transitions are defined over. You're right that Unicode-aware \w is huge if you build a full byte-based DFA for it. But that's why Rust's regex crate doesn't build full DFAs. It only builds the part of the DFA it needs (at search time). So you get the best of both worlds: reasonably fast compilation combined with fast search. (A big enough state machine will still ultimately overwhelm it and result in slower searches or large memory growth, depending on which trade off you pick. But a simple \w is handled just fine.)

Scaevolus 5y ago

The source code itself is stored as UTF-8, but the trigrams were represented as Unicode codepoints in the index. The last optimization packs the ASCII trigrams for efficiency.

kevincox 5y ago
But that's my point. Why not just store bytes, they you don't have to worry about packing, it is always packed. If I understand correctly they are using 8 bytes for 3 codepoints. They could instead use 3 bytes for 3 bytes. This would use significantly less memory and would rarely be less selective. (If that was a concern they could probably consider 4-grams instead of trigrams and still use less memory.) This also doesn't precude the splitting into the first 2 characters and last 1.
- Scaevolus 5y ago
  Oh, certainly, you could change the architecture to have byte-trigrams. These optimizations work without any large-scale architecture changes, making them safer to test and deploy, no data migrations or reindexing required!
roca 5y ago
I think the real question is: why not use trigrams of bytes (from the UTF8 representation) instead of Unicode codepoints? Seems like that would simplify everything. If they have data showing that doesn't work as well in practice, I'd love to know what it is, because I can't think of a reason off the top of my head why it wouldn't work well. Obviously it could only be worse in non-ASCII situations, which are already super-rare.
- bastawhiz 5y ago
  Because then you've potentially got a lot of trigrams for 4-byte Unicode characters that only contain the first three bytes of the character. Even if they're rare, you're effectively hamstringing anyone who uses a language that includes four byte characters or emoji. And for languages that use characters with three bytes, you're essentially indexing individual characters. Even in the case where you're using two byte characters, which is very common, your trigrams become one and a half characters. But moreover, the prefix of many of your trigrams is just going to be surrogate pair bytes. At this point, the whole point of building a reverse index is somewhat moot if you're indexing over parts of characters, byte sequences that are not useful on their own, and other such garbage. Yes, the ASCII happy path is fine, but you've essentially eliminated Unicode support entirely.
  - roca 5y ago
    > the prefix of many of your trigrams is just going to be surrogate pair bytes I'm not sure what you mean by this. Surrogate pairs are a UTF16 thing, not relevant here. > you've essentially eliminated Unicode support entirely. That's not obvious to me at all. In text containing non-ASCII characters, the trigrams that span UTF8 character boundaries are likely to give you the selectivity you need. > And for languages that use characters with three bytes, you're essentially indexing individual characters Not at all. The index would be a function of character pairs. It certainly could be worse but how much worse would depend on the characteristics of the source texts, which is why I think it would be really interesting to see whatever data Sourcegraph has on this.
    - bastawhiz 5y ago
      > Not at all. The index would be a function of character pairs. If it's a three byte trigram and it covers a three byte character, please explain how it could be anything other than a trigram containing a single character? If you want to cover a pair characters, you need six bytes. Which is also simply worse than the 42 bits you need to encode two Unicode code points as integers (as the author is doing now).

hanwenn 5y ago

Hi, Zoekt author here. There are a bunch of interesting replies, but they all miss the point. The reason you can't use bytes is a combination of two things: (1) code search supports case-insensitive matching. (2) the search algorithm uses distance between trigram occurrences to reduce the number of matches. With UTF-8, different case flavors of a character have different widths. For example, k (ascii k, 1 byte), K (ascii K, 1 byte) and K (unicode U+212A for Kelvin, 3 bytes). This messes up algorithm (2). The same consideration holds if you want to support searches where "a" also matches "á" and "ã". I did a talk on exactly this subject in 2017, which goes into more detail. The bit that explains it is here, https://youtu.be/_-KTAvgJYdI?t=602 https://youtu.be/_-KTAvgJYdI?t=602 . If you have more time, you can watch the entire thing, as it is entertaining, if I may say so :)

Sesse__ 5y ago
If you actually want to be UCA-compliant, though, it won't really help you to use codepoints. Different Unicode normalization, contractions and ignorables really mess up things. (In general, you can't search by case-folding if you want all the edge cases right; you have to apply the full Unicode collation algorithm.) I wonder if it's possible to store UCA weights instead of code points in the trigrams, but I haven't thought deeply about it, and it would surely affect indexing speed. In plocate, where I have this exact same issue, I solve it half-heartedly by using 3-byte trigrams and then constructing a whole bunch of alternatives, even if they differ in width. (I don't support accent-insensitive search and I don't support contractions, so locate ß won't find SS.) See https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp;h=678f520fd03cc7c11c63b3cae7f77e712196c56f;hb=HEAD#l197 https://git.sesse.net/?p=plocate;a=blob;f=parse_trigrams.cpp... — but it doesn't support the Kelvin case if it's in the filename and you give K on the command line.
kevincox 5y ago
> (1) code search supports case-insensitive matching. I'm not quite sure why this matters. Either you are case folding before you store and both cases are the same or you are expanding the query to consider all cases and both cases are the same. You are effectively storing "UTF-8" anyways. It is just whether you are storing 3 bytes or 3 characters. > (2) the search algorithm uses distance between trigram occurrences to reduce the number of matches. Could you not still measure this distance in codepoints? Or is there a benefit to tying this to the length of the trigrams? > The same consideration holds if you want to support searches where "a" also matches "á" and "ã". Well IIRC á can be two codepoints as well (if it isn't normalized) so don't you need to handle this case anyways?

benibela 5y ago

I use another regex library that does that and do not like it at all Something like \w makes the regex complexity explode. It spends more time building the regex than actually matching it.

burntsushi 5y ago
You can't get around the Unicode problem for free. If your state machine operates on codepoints, then your state machine is almost certainly very slow. Not only because you now need to do UTF-8 decoding, but you also probably need a sparse representation (e.g., a hash map) to deal with the large space of Unicode codepoints since that's what your transitions are defined over. You're right that Unicode-aware \w is huge if you build a full byte-based DFA for it. But that's why Rust's regex crate doesn't build full DFAs. It only builds the part of the DFA it needs (at search time). So you get the best of both worlds: reasonably fast compilation combined with fast search. (A big enough state machine will still ultimately overwhelm it and result in slower searches or large memory growth, depending on which trade off you pick. But a simple \w is handled just fine.)