marcospassos
commented
1 year ago @kaby76, run benchmarks with the profiler enabled to identify what is hurting the performance. I am interested in helping to fix it.
Open kaby76 opened 1 year ago
marcospassos
commented
1 year ago @kaby76, run benchmarks with the profiler enabled to identify what is hurting the performance. I am interested in helping to fix it.
kaby76
commented
1 year ago Looks like out of the gate of the start of the parse, the first call to GetCachedContext() should be for an empty context ("$"), breaking here.
But, that's not the same as in PHP. For the first context it's skipping past that short circuit, and stopping here, should have called this. The first call to the function is for an empty context in C#, but a singleton prediction context in PHP.
That's a major failure. Never mind. The method is recursive and I wasn't looking at the entire stack.
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 https://github.com/antlr/grammars-v4/pull/2977. So far, the ATN trace and parse trees are identical, which is great to see.
kaby76
commented
1 year ago 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. diffs.txt
marcospassos
commented
1 year ago 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.
kaby76
commented
1 year ago Not sure why, but debugging side-by-side of pdp7 grammar, input file s1.s, first breakpoint here has 'altsets' containing just 2 items in C#, 31 items in PHP. It should not be doing this. Never mind. Hard to switch between debuggers with different UI.
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.
kaby76
commented
1 year ago 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.
kaby76
commented
1 year ago 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.)
kaby76
commented
1 year ago marcospassos
commented
1 year ago kaby76
commented
1 year ago 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.
marcospassos
commented
1 year ago 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?
marcospassos
commented
1 year ago 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.
Where is it happening? Can you share more info, like a print of the stack or a link to the source where it happens?
kaby76
commented
1 year ago 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.
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.
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?
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.
marcospassos
commented
1 year ago 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.
kaby76
commented
1 year ago 10% seems to be saved just by rewriting the hash function for ATNConfig. The code before the change looks like this:
public function hashCode(): int
{
return Hasher::hash(
$this->state->stateNumber,
$this->alt,
$this->context,
$this->semanticContext,
);
}This code places all arguments into an array:
public static function hash(mixed ...$values): int
{
return self::hashArray($values);
}Then, each argument is processed in "if-then-else" to test each argument type, and dispatch to the appropriate compute function.
public static function hashValue(mixed $value): int
{
if (\is_string($value)) {
return \crc32($value);
}
if (\is_int($value)) {
return $value;
}
if ($value instanceof Hashable) {
return $value->hashCode();
}
if (\is_object($value)) {
return \spl_object_id($value);
}
if (\is_array($value)) {
return self::hashArray($value);
}
if (\is_bool($value) || \is_float($value) || \is_resource($value)) {
return (int) $value;
}
// Null
return 0;
}
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.
public function hashCode(): int
{
$hash = MurmurHash::Initialize(7);
$hash = MurmurHash::UpdateInt($hash, $this->state->stateNumber);
$hash = MurmurHash::UpdateInt($hash, $this->alt);
$hash = MurmurHash::UpdateHashable($hash, $this->context);
$hash = MurmurHash::UpdateHashable($hash, $this->semanticContext);
$hash = MurmurHash::Finish($hash, 4);
return $hash;
}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 hash_update requires a string as the second argument, so we need a way to convert the value to a string. My first attempt would be serializing the value since the result will be distinct strings for different data types. However, it's important to benchmark to make sure it won't hurt the performance:
$context = hash_init('murmur3a');
hash_update($context, \serialize($value));
// ...
$hash = hexdec(hash_final($context)); Also, it is worth benchmarking which performs better: murmur3a or xxh32.
xxh32 is said to be one of the fastest hashing algorithms around today.
marcospassos
commented
1 year ago 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.
marcospassos
commented
1 year ago @kaby76 any updates on the PHP target fixes?
kaby76
commented
1 year ago @kaby76 any updates on the PHP target fixes?
I've been working on the grammars-v4 build because of various issues there. https://github.com/antlr/grammars-v4/issues/2991 https://github.com/antlr/grammars-v4/issues/2988 https://github.com/antlr/grammars-v4/issues/2883
I do know there were some parse tree differences between PHP and other targets, so the work in PHP is not done.
Basically, https://github.com/antlr/antlr-php-runtime/pull/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.
marcospassos
commented
1 year ago 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.
Basically, the problem is that you can't do polymorphic methods in PHP.
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.
kaby76
commented
1 year ago 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.
marcospassos
commented
1 year ago Hey @kaby76, any updates on this?
kaby76
commented
1 year ago 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 https://github.com/antlr/antlr-php-runtime/pull/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 https://github.com/antlr/antlr-php-runtime/pull/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.