Optimize index data structure for search by supertype id.

So, instead of iterating over all subtypes and checking their supertypes
in string lists, we encode the supertype string id into int once, and
search for it in the denormalized supertype list.

This helps for files with really many classes and subtypes, such as
element.dart and as.dart (both interfaces, not implementations).

Before:
1537403233979 <= Computed implemented in 803 ms.
1537403239426 <= Computed implemented in 2518 ms.
1537403241893 <= Computed implemented in 811 ms.
1537403247675 <= Computed implemented in 2523 ms.
1537403249835 <= Computed implemented in 802 ms.
1537403255796 <= Computed implemented in 2478 ms.
1537403258396 <= Computed implemented in 809 ms.
1537403264560 <= Computed implemented in 2526 ms.
1537403267010 <= Computed implemented in 814 ms.
1537403274513 <= Computed implemented in 2491 ms.

R=brianwilkerson@google.com, paulberry@google.com

After:
1537415241048 <= Computed implemented in 421 ms.
1537415244042 <= Computed implemented in 873 ms.
1537415246189 <= Computed implemented in 402 ms.
1537415249342 <= Computed implemented in 853 ms.
1537415251478 <= Computed implemented in 420 ms.
1537415254756 <= Computed implemented in 877 ms.
1537415257278 <= Computed implemented in 492 ms.
1537415260514 <= Computed implemented in 864 ms.
1537415262864 <= Computed implemented in 421 ms.
1537415266170 <= Computed implemented in 888 ms.
Change-Id: I00e3b8d11ecc7da93816bc5575b7b79b91535d50
Reviewed-on: https://dart-review.googlesource.com/75631
Reviewed-by: Paul Berry <paulberry@google.com>
Reviewed-by: Brian Wilkerson <brianwilkerson@google.com>
Commit-Queue: Konstantin Shcheglov <scheglov@google.com>
7 files changed
tree: 5337ed7b469daa8902cba56434968720863aa17a
  1. .clang-format
  2. .gitattributes
  3. .gitconfig
  4. .github/
  5. .gitignore
  6. .gn
  7. .mailmap
  8. .packages
  9. AUTHORS
  10. BUILD.gn
  11. CHANGELOG.md
  12. CONTRIBUTING.md
  13. DEPS
  14. LICENSE
  15. PATENTS
  16. PRESUBMIT.py
  17. README.dart-sdk
  18. README.md
  19. WATCHLISTS
  20. build/
  21. client/
  22. codereview.settings
  23. dartdoc_options.yaml
  24. docs/
  25. pkg/
  26. runtime/
  27. samples-dev/
  28. samples/
  29. sdk/
  30. tests/
  31. third_party/
  32. tools/
  33. utils/
README.md

Dart

Dart is an open-source, scalable programming language, with robust libraries and runtimes, for building web, server, and mobile apps.

Using Dart

Visit the dartlang.org to learn more about the language, tools, getting started, and more.

Browse pub.dartlang.org for more packages and libraries contributed by the community and the Dart team.

Building Dart

If you want to build Dart yourself, here is a guide to getting the source, preparing your machine to build the SDK, and building.

There are more documents on our wiki.

Contributing to Dart

The easiest way to contribute to Dart is to file issues.

You can also contribute patches, as described in Contributing.

License & patents

See LICENSE and PATENTS.