search

tunnelvisionlabs / antlr4ts

Optimized TypeScript target for ANTLR 4
Other
636 stars 109 forks source link

Optimize ATNConfig types for JavaScript memory behavior #119

Open sharwell opened 8 years ago

sharwell commented 8 years ago

The implementation of ATNConfig uses two primary strategies for optimizing memory for this heavily-allocated type:

  1. Derived types are used to avoid storing unnecessary data where possible.
    • Most ATNConfig instances use SemanticContext.NONE as the semantic context, so storage is not provided for anything else in the base type.
    • Only ATNConfig instances in the lexer need to store a LexerActionExecutor, so storage is not provided for it in the base type (many more instances are allocated by the parser than the lexer).
  2. Bit fields are used to store three base properties in a single number.

The design decisions for optimizing memory are currently interleaved with design decisions for algorithmic correctness without explanation. See comments in the code review for #108 for several specific requests related to improving clarity.

:memo: This issue specifically relates to clarity and efficiency with respect to the performance characteristics of ATNConfig. A separate issue will be filed for questions related to the correctness characteristics of ATNConfig.

BurtHarris commented 8 years ago

In addition to memory behavior, there may be a substantial time/space tradeoff which is different in JavaScript engines than in conventional class-oriented languages. It is due to the inline-caching behavior that JavaScript engines like V8 and Chakra apply to runtime generated code. If the objects a particular piece of code change shape, it may cause an undesirable event called depotimization to occur. I don't know the details but there are V8 Flags available on nodeJS to determine how frequently deoptimization occurs which we should investigate as part of this work item.