Warm-up really doesn't help much, if anything at all, in performance #36
Comments
|
@kaby76, run benchmarks with the profiler enabled to identify what is hurting the performance. I am interested in helping to fix it. |
|
But, this looks very suspect. https://github.com/antlr/antlr-php-runtime/blob/dev/src/PredictionContexts/PredictionContext.php#L594. That's not correct because it's not calling the usual hash() and equals() functions for the map or set. I'll work on profiling after I start tracing how the parse works on multiple files and comparing that to C#. I made changes for grammars in v4 for PHP in PR antlr/grammars-v4#2977. So far, the ATN trace and parse trees are identical, which is great to see. |
|
OK, the table for PredictionContext was an array, not implemented as a Map, newed here. It was not working. I rewrote that to Map<PredictionContext,PredictionContext> as in C#, and it now has 20% speed up with warm-up. That's good, but not great. This code should be much much faster. There's more to find. My feeling is that it's in the engine that needs to handle ambiguity because it seems to be much much slower when the input exercises that code. |
|
WOW! With these fixes, we'll probably come close to the performance of other targets. I am looking forward to seeing the target performance ranking after theses changes. |
|
I agree--the PHP target should not be this slow. When there's no ambiguity, it is just as fast as the other targets. There's something wrong here. |
|
Although a minor issue, this code in PHP does not have a cardinality check for alt sets as done in C#. That would cut short the looping through the 31 elements--although not likely much of an issue. |
|
Bug, but not the problem https://github.com/antlr/antlr4/blob/76fa05c21b12b96a6c12a0a82e611ed9d87d5af4/runtime/CSharp/src/Atn/ATNConfigSet.cs#L280 (cached hash value should be reset to null, not -1, since everywhere else it's reset to null.) |
|
An absolutely humongous number of constructors are called for ATNConfig. It's easily 11x that for C# and Java. That's likely a symptom of the problem. Not sure why it's calling all this. A second possible problem is that there's no lazy evaluation of enumerables. Instead, lists and arrays created to iterator over. PHP does have a yield statement so this might be useful to short circuit loops in which not all elements are need in a list. |
Can you share the snippet where you think it may be problematic? |
Where is it happening? Can you share more info, like a print of the stack or a link to the source where it happens? |
Sigh. I didn't count two other constructors for ATNConfig (three total, here, here, and here). The number is identical between C# and PHP, and likely for Java (checking). That's actually very good news in that the PHP code looks like it's working identically to that in the other targets.
On the enumerables idea, there are numerous methods that have an IEnumerable parameter, and inside, a foreach over the IEnumerable. For example, here, with IEnumerable altsets. When iterating with a foreach, an enumerator is created and called to iterate through the enumerable, so it can be a lazy computation instead of requiring a collection. Unfortunately, I don't see methods that actually return IEnumerable, which means everything that is returned from a method is a scalar or a collection. For example, I was reading the code that creates a collection here. The full collection isn't needed always because this method returns a result on a partial analysis of the collection. Probably not very significant, but worth doing an analysis down the road. Still reading the code...and grasping at straws. Profiling just says closure_() is taking 17% the total run time in the method itself. Duh. But it also says hashArray() takes 10% of the total run time, too. That's why I am still looking over the hashing code. |
|
How far is PHP from other targets' performance? Also, how different is the time consumption of closure_ and hashCode calls between PHP and any other baseline? Not sure how frequently the same instance is hashed, but if it's significantly high, we can use a WeakMap to memoize immutable values. My guess is that it won't make any significant difference. |
|
10% seems to be saved just by rewriting the hash function for ATNConfig. The code before the change looks like this: This code places all arguments into an array: Then, each argument is processed in "if-then-else" to test each argument type, and dispatch to the appropriate compute function. But, we already know the types of each argument:
The alternative is to just call a function that handles the type directly, just as done with the other targets and "MurmurHash". Since PHP does not implement function overloading, we need to call an appropriately named method for the type. |
|
It could be even faster. PHP has native support for Murmur hash in streaming fashion, which means that the hash computation is done directly in C: $context = hash_init('murmur3a');
hash_update($context, 'foo');
hash_update($context, 'bar');
$hash = hexdec(hash_final($context)); Note that the $context = hash_init('murmur3a');
hash_update($context, \serialize($value));
// ...
$hash = hexdec(hash_final($context)); |
|
Also, it is worth benchmarking which performs better: xxh32 is said to be one of the fastest hashing algorithms around today. |
|
A reminder for us: after fixing all these possible causes of slowness, benchmark the target with JIT enabled. These hot functions are where JIT can be most beneficial. |
|
@kaby76 any updates on the PHP target fixes? |
I've been working on the grammars-v4 build because of various issues there. antlr/grammars-v4#2991 antlr/grammars-v4#2988 antlr/grammars-v4#2883 I do know there were some parse tree differences between PHP and other targets, so the work in PHP is not done. Basically, #34 fixes a number of problems with the data structures, and improves on the runtime speed by around 20% or more. There seems to be some improvement in rewriting the hash functions so they don't all funnel through hashValue(), which tests the parameter but the values are already known ints, strings, or what have you before calling this function. In that case, you can just call a function "hashInt()", etc. Basically, the problem is that you can't do polymorphic methods in PHP. But, when I was going through testing grammars-v4 against the PHP target, that's when I noticed still some parse tree differences. It really doesn't matter how fast a computation is if it's wrong to begin with. |
|
Yep. Do you intend to continue digging into it? My concern is this amazing work becoming outdated. Although I can't invest time in digging into the root cause right now, I can help with whatever else you need.
If you conclude that it really improves the performance, we can take some non-orthodox steps to emulate method overloading: $method = 'hash' . \gettype($value}
$this->{$method)($value);PHPStan will yell, and rightly so, but we can suppress the error. |
|
Yes, it is a concern when things change in the source and the PR becomes out of date. I do plan to return to this in a week. |
|
Hey @kaby76, any updates on this? |
Sorry, I haven't done anything since the last time you asked. Antlr 4.12 came out, and it seemed a good time to address all the problems with grammars-v4 testing, where it was taking 3+ hours for Github Actions to return the result of a build. That now takes ~5 minutes in most cases. With the change, grammars-v4 now is seeing many more PR's being submitted, and TypeScript is now being tested to boot. The changes I made in #34 are still valid I think. They are changes that make the PHP code operate in a more consistent manner with other targets. The primary focus of the changes was originally to get past the huge memory consumption. That's somewhat fixed, but still requires an option to PHP to run with more memory. https://github.com/antlr/grammars-v4/blob/432db2d76e898788c8f4f9a0666aefcd3fcd1fdd/_scripts/templates/PHP/run.sh#L1 I do plan on returning to the PHP code, likely after two more fixes:
I'm going to change #34 from draft to review since those changes get PHP to work slightly faster and produce parse ATN traces that are the same for more grammars. Please review. I plan to come back to PHP to build on these changes after completing the two tasks for grammars-v4. |
This is a sample of the performance times for the pdp7 grammar in grammars-v4. The following are a sample run of the parser on all examples, the first using successive warm-up.
The following are parse times without any warm-up .
For other targets, we usually see a 5x or 10x improvement for runtimes. E.g., C#:
These are the runtimes for non-warm-up parses.
PHP really should not be this slow, but especially, it should be faster for warm-up parsing. Yet it isn't.
The text was updated successfully, but these errors were encountered: