Performance woes. I'm appalled.
-
If switching on a char takes an inordinate amount of time, I'd sure be curious to know how your compiler does it. It ought to be the most efficient way of switching there is: A jump table indexed by the switch variable, loading the program counter. In the old days, when CPUs were slow, that was the only way to do it. (The first Pascal compiler I used could only take alternatives spanning a 256-value range, because that was the largest jump table it could generate.) Modern languages are far more flexible in their case expressions, often requiring the compiler to generate code like for an "if - elseif - elseif ... else" sequence. Maybe that is what your compiler has done here, maybe even generating "elseif"s for every char value, rather than collecting the "default" in an "else". If the compiler is scared of big jump tables, and therefore uses elseif-constructions, it rather should realize that this makes the code size grow far more than the size of a jump table! I am just guessing! But it sounds crazy that an indexed jump would kill your performance; it just doesn't sound right. I would look at the generated code to see what happens. If you can't make the compiler do an indexed jump, maybe you are better off writing it in longhand, building the jump table from labels :-). I guess that writing it explicitly as "if - elseif..." would be better. Then you could also do the most common case first, so that only a single test is required: "if (ch > '\t') {...}". I hate it when compilers force me to do the job that should be theirs, but maybe you have to, in this case!
That's pretty much where I'm at. I'm using gcc, which should be pretty good about optimizing. What gets me is it's not any faster whether I'm using no switches, or -g
Real programmers use butterflies
-
If switching on a char takes an inordinate amount of time, I'd sure be curious to know how your compiler does it. It ought to be the most efficient way of switching there is: A jump table indexed by the switch variable, loading the program counter. In the old days, when CPUs were slow, that was the only way to do it. (The first Pascal compiler I used could only take alternatives spanning a 256-value range, because that was the largest jump table it could generate.) Modern languages are far more flexible in their case expressions, often requiring the compiler to generate code like for an "if - elseif - elseif ... else" sequence. Maybe that is what your compiler has done here, maybe even generating "elseif"s for every char value, rather than collecting the "default" in an "else". If the compiler is scared of big jump tables, and therefore uses elseif-constructions, it rather should realize that this makes the code size grow far more than the size of a jump table! I am just guessing! But it sounds crazy that an indexed jump would kill your performance; it just doesn't sound right. I would look at the generated code to see what happens. If you can't make the compiler do an indexed jump, maybe you are better off writing it in longhand, building the jump table from labels :-). I guess that writing it explicitly as "if - elseif..." would be better. Then you could also do the most common case first, so that only a single test is required: "if (ch > '\t') {...}". I hate it when compilers force me to do the job that should be theirs, but maybe you have to, in this case!
Don't I feel stupid.
Approx stack size of local JSON stuff is 160 bytes
Read 1290495 nodes and 20383269 characters in 416.631000 ms at 45.603904MB/s
Skipped 1290495 nodes and 20383269 characters in 184.131000 ms at 103.187405MB/s
utf8 scanned 20383269 characters in 146.422000 ms at 129.761921MB/s
raw ascii i/o 20383269 characters in 58.902000 ms at 322.569692MB/s
raw ascii block i/o 19 blocks in 3.183000 ms at 5969.211436MB/sMuch better. I was using the wrong gcc options. I'm used to msvc
Real programmers use butterflies
-
What's frustrating is this simple case statement loses me about 7-8MB/s in throughput on something that currently tops out at about the low 60s on a good day.
switch(ch) {
case '\t': // tab
m_column+=TabWidth; // tabwidth is static const
break;
case '\n': // newline
++m_line;
// fall through
case '\r': // carriage return
m_column=0;
break;
default:
++m_column;
break;
}Real programmers use butterflies
Take a look at the [Compiler Explorer](https://godbolt.org/), and see if the assembler output make sense. Maybe an
ifstatement would produce better results, though it would be a less aesthetically pleasing, IMHO.Keep Calm and Carry On
-
Switching on characters is killing performance.
switch(ch) {
case '\t': // tab
m_column+=TabWidth; // tabwidth is static const
break;
case '\n': // newline
++m_line;
// fall through
case '\r': // carriage return
m_column=0;
break;
default:
++m_column;
break;
}This loses me 7-8MB/s in throughput on my machine pretty consistently. The problem is I switch on characters everywhere as this is a JSON parser. I can reduce some of my comparisons but not a lot of them because of the way my code is structured. The only other thing I can think of right now is building my own jump table schemes but I really don't want to do that so I'm trying to come up with something else.
Real programmers use butterflies
UTF8?
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
-
Take a look at the [Compiler Explorer](https://godbolt.org/), and see if the assembler output make sense. Maybe an
ifstatement would produce better results, though it would be a less aesthetically pleasing, IMHO.Keep Calm and Carry On
I'm a dunce. I had my compiler options set wrong. :laugh: This is my latest, somewhat fixed output, but it could be a lot faster. I want utf8 in the GB/s range or at least spitting distance of it on my machine
Approx stack size of local JSON stuff is 176 bytes
Read 1290495 nodes and 20383269 characters in 272.591000 ms at 69.701494MB/s
Skipped 1290495 nodes and 20383269 characters in 118.066000 ms at 160.926939MB/s
utf8 scanned 20383269 characters in 91.398000 ms at 207.882011MB/s
raw ascii i/o 20383269 characters in 57.443000 ms at 330.762669MB/s
raw ascii block i/o 19 blocks in 3.024000 ms at 6283.068783MB/sI just tried a branchless utf8 decoding routine but it proved to be slower than my original version. However, it's closer to something that could be converted to simd instructions so i'm exploring that more.
Real programmers use butterflies
-
UTF8?
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
Yeah, it's a unicode encoding format. Most characters are one byte so it's ascii-ish except for the extended character range. However, it's a bit involved to decode it. Implementing the JSON spec requires UTF-8 support.
Real programmers use butterflies
-
Yeah, it's a unicode encoding format. Most characters are one byte so it's ascii-ish except for the extended character range. However, it's a bit involved to decode it. Implementing the JSON spec requires UTF-8 support.
Real programmers use butterflies
Well, it triples the time needed. I would make it an option to choose ansi or ascii in the case where performance is an issue, but encoding isn't
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
-
Well, it triples the time needed. I would make it an option to choose ansi or ascii in the case where performance is an issue, but encoding isn't
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
The only issue with that is I'm trying to make it spec compliant, but i considered making it an option. I may yet, as it's quite a bit faster, but first i want to see how quick i can get the utf8 support. It won't triple the time needed if I can process 4 bytes at a time using simd :-D
Real programmers use butterflies
-
The only issue with that is I'm trying to make it spec compliant, but i considered making it an option. I may yet, as it's quite a bit faster, but first i want to see how quick i can get the utf8 support. It won't triple the time needed if I can process 4 bytes at a time using simd :-D
Real programmers use butterflies
honey the codewitch wrote:
but first i want to see how quick i can get the utf8 support.
Obviously! :-D
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
-
Don't I feel stupid.
Approx stack size of local JSON stuff is 160 bytes
Read 1290495 nodes and 20383269 characters in 416.631000 ms at 45.603904MB/s
Skipped 1290495 nodes and 20383269 characters in 184.131000 ms at 103.187405MB/s
utf8 scanned 20383269 characters in 146.422000 ms at 129.761921MB/s
raw ascii i/o 20383269 characters in 58.902000 ms at 322.569692MB/s
raw ascii block i/o 19 blocks in 3.183000 ms at 5969.211436MB/sMuch better. I was using the wrong gcc options. I'm used to msvc
Real programmers use butterflies
Are you familiar with the Compiler Explorer[^] ? It's a very useful tool for looking at the assembly generated by gcc and other compilers
-
Are you familiar with the Compiler Explorer[^] ? It's a very useful tool for looking at the assembly generated by gcc and other compilers
I like to do broad, algorithmic optimizations before I try to outsmart the compiler. I've gotten at least a 3 times speed improvement by changing my parsing to use strpbrk() over a memory mapped file. :-D
Approx stack size of local JSON stuff is 176 bytes
Read 1231370 nodes and 20383269 characters in 268.944000 ms at 70.646677MB/s
Skipped 1231370 nodes and 20383269 characters in 35.784000 ms at 530.963559MB/s
utf8 scanned 20383269 characters in 78.679000 ms at 241.487563MB/s
raw ascii i/o 20383269 characters in 58.141000 ms at 326.791765MB/s
raw ascii block i/o 19 blocks in 3.369000 ms at 5639.655684MB/sThe bold is the relevant line here. That's doing a parse of the bones of the document (looking for {}[]") in order to skip over it in a structured way. That style of parsing is used for searching, for example, when you're trying to find all ids in a document. It's using the mmap technique i mentioned. Here's snagging all "id" fields out of a 20MB file and reading their values.
Approx stack size of local JSON stuff is 152 bytes
Found 40008 fields and scanned 20383269 characters in 34.664000 ms at 548.119086MB/sThe bytes used stuff is roughly how much memory the query takes - including the sizes of the JsonReader and LexSource member variables.
Real programmers use butterflies
-
Read 1231388 nodes and 20383269 characters in 1069.479000 ms at 17.765660MB/s
Skipped 1231388 nodes and 20383269 characters in 534.699000 ms at 35.534011MB/s
utf8 scanned 20383269 characters in 377.561000 ms at 50.322994MB/s
raw ascii i/o 20383269 characters in 62.034000 ms at 306.283651MB/s
raw ascii block i/o 19 blocks in 49.023000 ms at 387.573180MB/sThe first line is full JSON parsing The second line is JSON "skipping" - a minimal read where it doesn't normalize anything it just moves as fast as possible through the document. The third line is ut8 reading through my input source class but without doing anything JSON related The fourth line is calling fgetc() in a loop The fifth line is falling fread() in a loop and then scanning over the characters in each block (so i'm not totally cheating by not examining characters) The issue here is the difference between my third line and the fourth line (utf8 scan vs fgetc). The trouble is even when I removed the encoding it made no measurable difference in speed. Underneath everything both are using fgetc. Even when I changed mine to block read using fread() it didn't speed things up. I'm at a loss. I'm not asking a question here, mostly just expressing frustration because i have not a clue how to optimize this.
Real programmers use butterflies
-
I suspect that the utf8 scanning is using fgetc underneath to return one character at a time. This would greatly simplify the implementation of the utf8 scanner.
What I use under the covers depends on what kind of LexSource you use. Mainly I use memory mapped files now, for speed, but I'm implementing one using fread and buffered access and we'll see how that stacks up. I'm very nearly breaking 600MB/s of JSON searching on my machine. :)
Real programmers use butterflies