Project

Profile

Help

Bug #6607

open

Type-checking of maps - performance issue

Added by Michael Kay 13 days ago. Updated 2 days ago.

Status:
In Progress
Priority:
Low
Assignee:
Category:
Performance
Sprint/Milestone:
-
Start date:
2024-12-08
Due date:
% Done:

0%

Estimated time:
Legacy ID:
Applies to branch:
12, trunk
Fix Committed on Branch:
12, trunk
Fixed in Maintenance Release:
Platforms:
.NET, Java

Description

Shown by QT3 test case fn-parse-json-056

In order to test whether a map conforms to the required type map(*), the code in TypeChecker.staticTypeCheck() is calling map.getItemType() which is an expensive operation as it involves examining all the entries in the map.

Actions #1

Updated by Michael Kay 9 days ago

What's happening here is a call on map:keys(parse-json('....')) where the call on parse-json() is preevaluated to a Literal map before the call on map:keys is type checked. The type checking code tries to determine the static type of the expression being passed as the first argument, and in this case the expression is a Literal, so it ends up trying to determine the item type of the map.

Perhaps rather than calling the method Expression.getItemType() there should be a method Expression.isItemTypeSubtypeOf(X) .That's a rather substantial change but the new method could be given a default implementation that calls getItemType(), and could have a custom implementation for literals.

Alternatively, and perhaps more simply, Literal could return true for implementsStaticTypeCheck(), in which case it would call Literal.staticTypeCheck(), which achieves much the same thing. Current expressions that implement this method are things like Block and Choose, which go on to check not just that the expression as a whole delivers the right type, but that every operand does so.

Actions #2

Updated by Michael Kay 9 days ago

Added a fast path to TypeChecker.staticTypeCheck:

        if (supplied instanceof Literal && ((Literal)supplied).isInstance(req, th)) {
            return supplied;
        }

This is going to catch all cases where a function is called with a literal argument that matches the required type, so the benefit could be substantial.

Actions #3

Updated by Michael Kay 7 days ago

  • Status changed from New to Resolved
  • Applies to branch 12, trunk added
  • Fix Committed on Branch 12, trunk added
  • Platforms .NET, Java added
Actions #4

Updated by Michael Kay 2 days ago

  • Status changed from Resolved to In Progress

This code causes a performance regression for type-checking of an expression such as 1 to 1000000, where Expression.getItemType() is fast, but checking the type of the instance is slow. That particular example is easily fixed in Literal.isInstance() by special-casing, but there may be other cases where Expression.getItemType() is more effective than Literal.isInstance().

Please register to edit this issue

Also available in: Atom PDF