7 ms·

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

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).
      - roca 5y ago
        Because there are trigrams crossing the boundaries between characters. E.g. given the bytes ABCXYZ, the trigrams are not just ABC and XYZ but also BCX and CXY. Then the question is, assuming ABC, XYZ, BCX and CXY are all present in a document, what is the probability that ABCXYZ is present in the document? If it's close to 1, then the byte trigram index is about as powerful as a character bigram index. Of course it's also true that bigrams might be inadequately selective, but the underlying alphabet is probably larger than ASCII if it encodes to 3 bytes in UTF8. Again I'm not arguing that trigrams-over-bytes is necessarily the best option here, just that it's simpler and a decision to do trigrams over Unicode characters needs data to justify it, and I'd love to know what that data is.
        5y ago
- Sesse__ 5y ago
  It's entirely possible to do so, and I do it in plocate, which solves a similar problem in pretty much the same way. But it's non-ideal for case-insensitive matching (see previous comment).

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).
    - roca 5y ago
      Because there are trigrams crossing the boundaries between characters. E.g. given the bytes ABCXYZ, the trigrams are not just ABC and XYZ but also BCX and CXY. Then the question is, assuming ABC, XYZ, BCX and CXY are all present in a document, what is the probability that ABCXYZ is present in the document? If it's close to 1, then the byte trigram index is about as powerful as a character bigram index. Of course it's also true that bigrams might be inadequately selective, but the underlying alphabet is probably larger than ASCII if it encodes to 3 bytes in UTF8. Again I'm not arguing that trigrams-over-bytes is necessarily the best option here, just that it's simpler and a decision to do trigrams over Unicode characters needs data to justify it, and I'd love to know what that data is.
      - 5y ago
Sesse__ 5y ago
It's entirely possible to do so, and I do it in plocate, which solves a similar problem in pretty much the same way. But it's non-ideal for case-insensitive matching (see previous comment).