That search doesn't handle head/tail overlaps, but otherwise it's a good approximation. I'm surprised it isn't faster; I think I got a few hundred MB/s on trie-based matching.
Protip: bring benchmarks like this to your meeting with the sales rep.
I think the point was just to test each string against the query for equality. The benchmark could be slightly tweaked to test each string against the query for substring inclusion or regular expression match, but I suspect the results would only change by the cost of the test predicate.
Not necessarily when comparing different language, as they might allow different optimizations. For example, you'd be able to compare several bytes at a time with C if you pad the strings, while node.js' V8 is unlikely to optimize that far.
I'm actually somewhat surprised it wasn't faster. I may play with this and see how fast I can get it to go.
Edit: After a number of attempts (such as using Golang's regexp library or strings.Contains()), I wasn't able to speed it up much. Interestingly, grep performs the same search in about 5ms on my machine.
EDIT:
Interestingly, there seems to be an internal Boyer-Moore implementation in Golang's strings package[3], though it only appears to be used in strings.Replace("")[4]
That's a nice overview by the author. I've been fond of this blog post which goes into the main trick grep does besides Boyer-Moore and unrolling the loop that'll make it beat a by-the-book implementation with unrolling: http://ridiculousfish.com/blog/posts/old-age-and-treachery.h...
Go's concurrency model defines that memory writes in one goroutine won't be observable in another until a context switch can happen (e.g. by send/recv on a channel). In practice, newly spawned goroutines often don't get the chance to run at all until that context switch. But yeah, it's not a good idea to rely on this behavior here.
Go's goroutines launch on threads when multiple CPUs are available. They have all the race conditions of C code. Memory writes certainly are visible on other goroutines.
Goroutines do not map to OS threads 1:1. Whether the scheduler decides to spawn a thread or not is its own, entirely private decision. No action is guaranteed to be taken until scheduling occurs.
Well, from that spec: "When multiple goroutines access a shared variable v, they must use synchronization events to establish happens-before conditions that ensure reads observe the desired writes."
However, that very specifically does NOT say that writes may not be observed BEFORE synchronization events. They MAY.
Under "Incorrect Synchronization": "Note that a read r may observe the value written by a write w that happens concurrently with r. Even if this occurs, it does not imply that reads happening after r will observe writes that happened before w."
These memory ordering rules are the same as C, C++ or machine code. Go makes no special effort to avoid the natural machine behavior of x86, ARM or MIPS.
And on goroutine spawning and execution order, I have observed both behaviors. Sometimes Go will continue on the current goroutine before launching other goroutines. Other times the new goroutines begin executing immediately. It's possible that some other, background goroutine is causing a scheduling event, but if so it's so random that no one could predict it.
Maybe i'm blind - but i'm not seeing where the benchmark results are? Also, is this code the same code that you actually ran? For ruby, i notice you are outputting 'contens' not 'contents' so i imagine you would get a runtime error?
I did some benchmarking for a dictionary app a while back, and the fastest I could get was strstr(), if I recall correctly. It substantially beat std::string::find(). Using a loop is bound to give terrible performance; for large data you should be using one of the string-search algorithms (which strstr() surely does). And given the very large search string, those string-search algorithms should be able to skip large chunks at a time.
Here's a small version that allocates 200 MB of uninitialized memory.
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
int size = 200 * 1024 * 1024;
char *bytes = malloc(size);
bytes[size - 1] = '\0';
strstr(bytes, "788bbd6b12d79a4ee18e36a8a264fb496465c71b7932a965ed731397b7c97d14");
return 0;
}
> gcc test.c
> time ./a.out
real 0m0.006s
user 0m0.002s
sys 0m0.002s
(Since the author ignores time to read off disk, I figure uninitialized memory should be comparable. The chances of strstr() actually finding anything are pretty slim, but I ran it a number of times just to be sure, with the same results.)
Note that strstr will stop as soon as you have a 0 byte so this is not a fair comparison.
Uninitialized (practically often zeroed) also produces different results from random and explicitly zeroed, since I assume it affects how often it can fail fast.
#define _GNU_SOURCE
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
int main(int nargs, char ** args)
{
struct timespec start;
struct timespec end;
int mode = atoi(args[1]);
const char * needle = "788bbd6b12d79a4ee18e36a8a264fb496465c71b7932a965ed731397b7c97d14";
const int N = 200*1024*1024 ;
char * haystack = malloc(N + sizeof(needle));
strcpy(haystack+N,needle);
printf("Mode is %s\n" , mode == 0 ? "zeroed" :
mode == 1 ? "random" :
"uninitialized");
if (mode == 0)
{
memset(haystack,0,N);
}
if (mode == 1)
{
FILE * urandom = fopen("/dev/urandom","r");
int nread = fread(haystack,1,N,urandom);
fclose(urandom);
if (nread < N)
{
fprintf(stderr,"read returned %d\n",nread);
}
}
clock_gettime(CLOCK_REALTIME, &start);
void * found = memmem(haystack,N+sizeof(needle),needle,sizeof(needle));
clock_gettime(CLOCK_REALTIME, &end);
printf("Took %g secs to find string at offset of %llu\n", end.tv_sec - start.tv_sec + 1e-9*(end.tv_nsec - start.tv_nsec), found-(void*)haystack);
return 0;
}
$ gcc test_find.c -o test_find
$ ./test_find 0
Mode is zeroed
Took 0.0147023 secs to find string at offset of 209715200
$ ./test_find 1
Mode is random
Took 0.129951 secs to find string at offset of 209715200
$ ./test_find 2
Mode is uninitialized
Took 0.0371922 secs to find string at offset of 209715200
Note that if you malloc that big of a block, it's going to come directly from a MAP_ANONYMOUS mmap, and so it will be zero initialized!
Your uninitialized mode is slower than zeroed, but nowhere near as slow as random.
The difference between initialized and uninitialized may be due to page faults: in the uninitialized case, the search is touching the memory for the first time. Maybe we're seeing TLB misses?
Yeah I was expecting the uninitialized to be the same as the zeroed case for that reason, but was surprised to see a (slightly) different result.
Edit: you are almost certainly right. I added a getrusage call before and after, and we have ~50k soft page faults in the uninitialized case and ~2 in the zeroed case during the memmem.
I meant something different, your implementation is unable to find the pattern if it does not start at an index divisible by 64. You are effectively only searching through 3,125 MiB instead of 200 MiB.
I once wrote a scanner similar to this for Symantec in C++. As I recall it used a hybrid between the Wu-Manber and Boyer-Moore search algorithms to search a million lines of text for thousands of signatures simultaneously in approx 0.004s as I recall.
0.25s for 200MB (in memory) seems pretty slow for a modern CPU (800MB/s) which is more than an order of magnitude below what you would expect from main memory.
This isn't super surprising to me. String comparisons are super slow if not handle with care, and even then may be surprisingly slow. This does a LOT of string comparisons.
EDIT: I believe paper trail does or did have a limitation on case sensitive searching. You can imagine why they may be doing this if you consider the performance implications.
This is actually something I'm trying to figure out. I currently use (and pay for) Scalyr, which is the best of the bunch (super fast, flexible alerting) but I hate shipping my log data there. It just seems like a potential attack surface I am not really happy about.
Is there anything open source that I can run in a docker container somewhere on the internets that allows me to create custom alerts, extract data, create charts and dashboards?
As far as I've been able to tell, ELK and Graylog are still pretty much the only answers here. Either one will set you back at least three Docker containers and take a bit of configuration, and while they both have dashboarding capabilities I'm not sure if they're any good. You can plug Elasticsearch into Grafana though so there's that.
Elasticsearch + Kibana/Grafana. The next version will opensource XPack[1] which has some support for alerting[2]. You can also use Grafana with ES and setup alerts there (I think)
For example, I am wary about who has access to my log data. I know that theoretically, I "invite" your support team, and can revoke it, but without an understanding of the architecture behind Scalyr, I am afraid this is just lip service.
"But isn't transient log storage a popular use case, and if so why don't any services optimize for it?"
Well I could start with "define transient"! I also note your unhappiness with third party logging facilities. I also note you went very DIY.
A three node ES cluster with a Graylog on the front can ingest quite a lot of logs for a reasonable time outlay in learning how it hangs together. A bit of tuning might be required.
I don’t have a computer at hand, but I imagine it would be a lot shorter (and likely faster due to algorithmic optimisations) to use bytes.Index. As other have pointed out, 1 GB/s seems slow. I would expect that performance when reading from disk.
(Also, iterating over indexes is not too idiomatic in Go. You can iterate both the index and value using `range`, just like enumerate in Python.)
Turned out bytes.Index is initially similar or slower in speed, but search time goes down to 40ms as soon as you lop off the last byte.
For strings over (on my machine) 63 bytes, bytes.Index uses a rolling Rabin-Karp hash. For this data it's ~25% slower than the loop to search. However, that evens out if you make the whole file hex, which makes the search loop have some branch mispredictions. (Also, the simple loop search isn't complete! More below.) The R-K search is more reasonable than this one comparison makes it sound; it avoids bad worst-case behavior when there are a lot of partial matches. (Also, it may be less optimized because authors think most bytes.Index searches will be for short bits of data.)
Relatedly, the loop search doesn't back up its position when it discovers a partial match isn't a complete match, which means it's incorrect; it won't find a real match that overlaps with a false match (a prefix of a match). Like, when I made a file that contained "07123E1F482356C415F684407123E1F482356C415F684407A3B8723E10B2CBBC0B8FCD6282C49D37C9C1ABC", it didn't find the match starting at the second 071... because it overlaps with a prefix of a match (at the start of the string) that didn't turn out to be a full match. (The overlap is two digits here, but same thing would come up if it were one digit.)
Searching for shorter strings, Index on Intel platforms uses AVX/SSE search. If you're going to search for long strings and feel lucky, you could search for a prefix of whatever your platform's max SIMD-searchable length is, then check if it's a full match. If so, you're done; if not, keep searching starting at the next byte. In case of pathological data you could bail out to the safe R-K approach after n false matches, like one of Index's existing strategies does. It might be something for someone who wants a stdlib patch to try submitting to Go, though it might also be that they see it as too much of a corner case to merit complicating things more.
I wonder how long a simple grep over a 200MB file takes on linux. I guess if you put the 200MB file on a ramdisk then you could easily do it from memory.
A single frame of Quake is 800x600=1mb of memory, and quake ran at 30fps on a pentium-233 in software. That's 30mb per second circa 1995. So your times all seem extremely slow to me. You should be getting a couple orders of magnitude better speeds. Try it in rust!
The Ruby implementation looks wrong. He's shoving the file into an array:
contents = contents.read.each_byte.to_a
When really he should be streaming each byte from the file. I suppose he should do that for all of the implementations (or just use grep & cat?), but Ruby objects are annoyingly expensive since there's so much bloat.
The ruby version looked a bit odd to me. It would be unusual to not use regex in this context.
I'm not sure if this is in the spirit of the test, but using regex reduced the time from 27s to 0.04s on my machine.
require 'benchmark'
contents = File.read("/tmp/200mb.txt")
find = "07123E1F482356C415F684407A3B8723E10B2CBBC0B8FCD6282C49D37C9C1ABC"
result = nil
elapsed = Benchmark.realtime do
result = (contents =~ /#{find}/)
end
puts "Found at index #{result} in #{elapsed}s"
(The search string was placed at the end of a 200mb file)
So, if this is to measure the relative speed of a naive algorithm across multiple languages then great. If this is an attempt to measure how fast a single cpu can scan memory for a string then there are better algorithms. This is just one: [1]
Not wanting to be the 'Old Man Yells At Cloud' figure, but this is a perfect illustration of how not to do it, particularly multithreading in Go before using a reasonable algorithm.
Searching for a long string like this is preposterously easy. You can use a classical algorithm, or, given you are looking for a 64 byte long string, you could do a strided inspection - every 32 bytes, look to see if you have a 4-gram from the first 35 bytes of the string. More or less anything works as almost any reasonable string searching mechanism can outrun memory bandwidth.
Depends on how often you need to search. The implementation of the parallel linear search in Go is a lot easier to get right than what you’re recommending.
Though I would certainly agree that paying for more vm cores just so you can do a linear search on each of them is a bit silly
The linear search code should probably be in a library, and in fact often is, if you have the GNU extension memmem().
I'm also not convinced that it's that hard. This seems to be the new cult; just because someone buggered up binary search with an integer overflow once, we're not going to write non-pathological algorithms anymore?
I’m not saying it’s a bad idea to implement it, but there’s a greater time cost, and if the performance gains aren’t worth the effort, then there’s no reason to make the improvement
Fair enough. I guess you would figure out how long it takes to either clag the code from somewhere else or write it yourself and plug in the math at the bottom of the page (as they are trying to quantify the value of doing this).
I strongly suspect dragging in memmem() would be the most cost effective way of doing this and run in the most places, even if it's a non-standard GNU libc extension.
Otherwise (single core) golang code seems to be just a test whether the compiler is smart enough to remove branch in this code:
if (b[n]) == (find[found]) {
found += 1
} else {
found = 0
}
I wouldn't be too surprised if golang compiler generates superfluous range checks costing even more performance. At least golang 1.4 seemed to generate a lot of unnecessary checks in code I optimized a few years ago. Hopefully newer versions are better.
The fastest, Golang at slightly over 2.8GB/s, is still surprisingly slow for modern (as in, under 10 years old) hardware. I just wrote a similar linear search in Asm using the not-so-fast REPNZ SCASB/CMPSB instructions and got 6GB/s on an i7 860 from 2009.
If you're just scanning for the string then algorithms like BMH can do up to x times memory bandwidth, where x is the length of the string, since they start matching from the end and can skip over chunks of x bytes at once.
This article from someone with a rather... distinctive style shows >10GB/s on 5-year-old hardware with target strings only slightly over 50 bytes:
I recall repne scasb was significantly slower than the equivalent loop unrolled a few times. Not sure if that's still the case but it was something like 2x slower.
The algorithm works as follows: Read 5 characters. Is that in the dictionary? No. What about the first 4? No. 3? No. 2? Yes! Copy to the output string, add a space, slide along 2 characters. Repeat.
Searching a 5 MB dictionary repeatedly like this was too slow. I made it a little faster by splitting the dictionary based on the number of characters in the word (fiveWords, fourWords, threeWords, twoWords). It's still slow, though. I have to run it in local JavaScript, because I don't have a server. Any suggestions?
On a totally different extreme, the iTunes Store's EPF data (freely available!) is 55 GB of text. I'd like to sort out Artist names by Producer. To grep the file takes 30 mins. Is there a faster way?
Third, my algorithm for offline StackOverflow was optimised for disk space. I search the index of titles as 200MB of plain text to get the post ID. Then I use dd to get a 4KB chunk of the tar.bz2 compressed file. I can read it using bzip2recover. Then I check if the post ID is there, and binary search like that. It's slow (5 seconds to load) but doesn't waste my precious disk space, and I can be patient when I need offline StackOverflow.
As for offline StackOverflow, you should use a database engine like SQLite or Redis to manage indexing into smaller blocks of compressed post data on-disk, or store the posts directly in the database and keep the database files in a filesystem like BTRFS that supports online compression.
I would put your dictionary into a prefix tree if some sort, and the first implementation I would reach for is a trinary tree [1]. As you scan your input, walk the tree. Each time you get to the end of the tree, insert a space one go back to the root. Once the tree is built it’s O(length of input) [2] regardless if dictionary size.
74 comments
[ 4.6 ms ] story [ 157 ms ] threadProtip: bring benchmarks like this to your meeting with the sales rep.
Edit: After a number of attempts (such as using Golang's regexp library or strings.Contains()), I wasn't able to speed it up much. Interestingly, grep performs the same search in about 5ms on my machine.
One big takeaway is that grep doesn't simply traverse the string linearly, instead using the Boyer-Moore algorithm [2].
1: https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug...
2: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sea...
EDIT: Interestingly, there seems to be an internal Boyer-Moore implementation in Golang's strings package[3], though it only appears to be used in strings.Replace("")[4]
3: https://golang.org/src/strings/search.go
4: https://golang.org/src/strings/replace.go?h=stringFinder
https://github.com/BurntSushi/ripgrep
Go's goroutines launch on threads when multiple CPUs are available. They have all the race conditions of C code. Memory writes certainly are visible on other goroutines.
From the very official spec? https://golang.org/ref/mem
Goroutines do not map to OS threads 1:1. Whether the scheduler decides to spawn a thread or not is its own, entirely private decision. No action is guaranteed to be taken until scheduling occurs.
However, that very specifically does NOT say that writes may not be observed BEFORE synchronization events. They MAY.
Under "Incorrect Synchronization": "Note that a read r may observe the value written by a write w that happens concurrently with r. Even if this occurs, it does not imply that reads happening after r will observe writes that happened before w."
These memory ordering rules are the same as C, C++ or machine code. Go makes no special effort to avoid the natural machine behavior of x86, ARM or MIPS.
And on goroutine spawning and execution order, I have observed both behaviors. Sometimes Go will continue on the current goroutine before launching other goroutines. Other times the new goroutines begin executing immediately. It's possible that some other, background goroutine is causing a scheduling event, but if so it's so random that no one could predict it.
I'd love to see this comparison expanded to a few other languages (particularly C/C++ with custom memory allocation).
EDIT: Reworking the code.
Here's a small version that allocates 200 MB of uninitialized memory.
(Since the author ignores time to read off disk, I figure uninitialized memory should be comparable. The chances of strstr() actually finding anything are pretty slim, but I ran it a number of times just to be sure, with the same results.)This is on a 2012 MacBook Pro.
Uninitialized (practically often zeroed) also produces different results from random and explicitly zeroed, since I assume it affects how often it can fail fast.
Your uninitialized mode is slower than zeroed, but nowhere near as slow as random.
The difference between initialized and uninitialized may be due to page faults: in the uninitialized case, the search is touching the memory for the first time. Maybe we're seeing TLB misses?
Edit: you are almost certainly right. I added a getrusage call before and after, and we have ~50k soft page faults in the uninitialized case and ~2 in the zeroed case during the memmem.
Sounds like you implicitly assumed the match will be aligned at a 64 byte boundary which makes the task much easier and 4 GiB/s a pretty slow result.
Unsure why the previous result was way off, but I am lacking time for fun tonight :)
IOW, your code is not doing remotely same task as the blog post ones.
Edit: "Typoed" 1 GB instead of 200 MB. Oops. The point holds.
There can be a lot of performance left on the table even in standard library implementations: http://0x80.pl/articles/simd-strfind.html
Depending on the requirements, sliding a window through doing byte comparisons may be better. https://golang.org/src/bytes/bytes_decl.go?s=522:550#L7
EDIT: I believe paper trail does or did have a limitation on case sensitive searching. You can imagine why they may be doing this if you consider the performance implications.
Is there anything open source that I can run in a docker container somewhere on the internets that allows me to create custom alerts, extract data, create charts and dashboards?
[1] https://www.elastic.co/products/x-pack/open
[2] https://www.elastic.co/products/x-pack/alerting
Well I could start with "define transient"! I also note your unhappiness with third party logging facilities. I also note you went very DIY.
A three node ES cluster with a Graylog on the front can ingest quite a lot of logs for a reasonable time outlay in learning how it hangs together. A bit of tuning might be required.
I suspect I'm not your target market.
(Also, iterating over indexes is not too idiomatic in Go. You can iterate both the index and value using `range`, just like enumerate in Python.)
https://golang.org/pkg/bytes/#Index
For strings over (on my machine) 63 bytes, bytes.Index uses a rolling Rabin-Karp hash. For this data it's ~25% slower than the loop to search. However, that evens out if you make the whole file hex, which makes the search loop have some branch mispredictions. (Also, the simple loop search isn't complete! More below.) The R-K search is more reasonable than this one comparison makes it sound; it avoids bad worst-case behavior when there are a lot of partial matches. (Also, it may be less optimized because authors think most bytes.Index searches will be for short bits of data.)
Relatedly, the loop search doesn't back up its position when it discovers a partial match isn't a complete match, which means it's incorrect; it won't find a real match that overlaps with a false match (a prefix of a match). Like, when I made a file that contained "07123E1F482356C415F684407123E1F482356C415F684407A3B8723E10B2CBBC0B8FCD6282C49D37C9C1ABC", it didn't find the match starting at the second 071... because it overlaps with a prefix of a match (at the start of the string) that didn't turn out to be a full match. (The overlap is two digits here, but same thing would come up if it were one digit.)
Searching for shorter strings, Index on Intel platforms uses AVX/SSE search. If you're going to search for long strings and feel lucky, you could search for a prefix of whatever your platform's max SIMD-searchable length is, then check if it's a full match. If so, you're done; if not, keep searching starting at the next byte. In case of pathological data you could bail out to the safe R-K approach after n false matches, like one of Index's existing strategies does. It might be something for someone who wants a stdlib patch to try submitting to Go, though it might also be that they see it as too much of a corner case to merit complicating things more.
That would be my first and dirty approach.
Sample code: https://pastebin.com/duYF2QfE
This was on a "Early 2015" rMBP with a 3.1 GHz i7.
That way both golang and Java will be performing proper unicode code point indexing.
Of course the optimization you made makes sense, but I think it'd be fair for the golang version to do same.
I'm not sure if this is in the spirit of the test, but using regex reduced the time from 27s to 0.04s on my machine.
(The search string was placed at the end of a 200mb file)You might want to read about classical string search algorithms. Your naive algorithm is straightforward but far from ideal.
Now I feel bad for wasting an hour wrestling with Go weirdness to get my program to compile.
Searching for a long string like this is preposterously easy. You can use a classical algorithm, or, given you are looking for a 64 byte long string, you could do a strided inspection - every 32 bytes, look to see if you have a 4-gram from the first 35 bytes of the string. More or less anything works as almost any reasonable string searching mechanism can outrun memory bandwidth.
Or you could go use my old project (https://github.com/intel/hyperscan) and then you could look for regexes too. :-)
Though I would certainly agree that paying for more vm cores just so you can do a linear search on each of them is a bit silly
I'm also not convinced that it's that hard. This seems to be the new cult; just because someone buggered up binary search with an integer overflow once, we're not going to write non-pathological algorithms anymore?
I strongly suspect dragging in memmem() would be the most cost effective way of doing this and run in the most places, even if it's a non-standard GNU libc extension.
Edit: Clarified I'm talking about string "find" and not byte array "b".
Otherwise (single core) golang code seems to be just a test whether the compiler is smart enough to remove branch in this code:
I wouldn't be too surprised if golang compiler generates superfluous range checks costing even more performance. At least golang 1.4 seemed to generate a lot of unnecessary checks in code I optimized a few years ago. Hopefully newer versions are better.Ranging a string does return unicode runes, however, but ranging is obviously O(n) anyway.
https://play.golang.org/p/oyaChPTb576
If you're just scanning for the string then algorithms like BMH can do up to x times memory bandwidth, where x is the length of the string, since they start matching from the end and can skip over chunks of x bytes at once.
This article from someone with a rather... distinctive style shows >10GB/s on 5-year-old hardware with target strings only slightly over 50 bytes:
https://www.codeproject.com/Articles/250566/Fastest-strstr-l...
https://pingtype.github.io
The algorithm works as follows: Read 5 characters. Is that in the dictionary? No. What about the first 4? No. 3? No. 2? Yes! Copy to the output string, add a space, slide along 2 characters. Repeat.
Searching a 5 MB dictionary repeatedly like this was too slow. I made it a little faster by splitting the dictionary based on the number of characters in the word (fiveWords, fourWords, threeWords, twoWords). It's still slow, though. I have to run it in local JavaScript, because I don't have a server. Any suggestions?
On a totally different extreme, the iTunes Store's EPF data (freely available!) is 55 GB of text. I'd like to sort out Artist names by Producer. To grep the file takes 30 mins. Is there a faster way?
Third, my algorithm for offline StackOverflow was optimised for disk space. I search the index of titles as 200MB of plain text to get the post ID. Then I use dd to get a 4KB chunk of the tar.bz2 compressed file. I can read it using bzip2recover. Then I check if the post ID is there, and binary search like that. It's slow (5 seconds to load) but doesn't waste my precious disk space, and I can be patient when I need offline StackOverflow.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
As for offline StackOverflow, you should use a database engine like SQLite or Redis to manage indexing into smaller blocks of compressed post data on-disk, or store the posts directly in the database and keep the database files in a filesystem like BTRFS that supports online compression.
1: https://en.m.wikipedia.org/wiki/Ternary_search_tree
2: for a fixed alphabet size. It’s really closer to O(dictionary size * log(alphabet size)) if that increases with dictionary size.