1 of 86

Indexing or �How We Made Indexes Shared and Faster

Eugene Petrenko

​

@jonnyzzz

2 of 86

How may Find Usages work?

3 of 86

4 of 86

Find Usages

5 of 86

Find Usages

6 of 86

Rename Refactoring

7 of 86

Old Times

8 of 86

Simple Syntax Highlighting

9 of 86

Smart Code Inspections & Highlighting

10 of 86

Experiment: Full Text Search

  • Project: IntelliJ IDEA Community
    • On GitHub - https://github.com/jetbrains/intellij-community
    • Apache 2.0 License
    • 120k files / 4.5Gb total
    • with 69k Java files, 7k Kotlin files consuming 212mb

​

11 of 86

Grepping IntelliJ Community

  • Call on console “fgrep -R -e ‘Swapper32’ .”
    • takes ~80 seconds on macOS
    • takes ~1.5 seconds on Linux

12 of 86

Grepping IJ Community

13 of 86

Grepping IntelliJ Community

  • Call on console “fgrep -R -e ‘Swapper32’ .”
    • takes ~80 seconds on macOS
    • takes ~1.5 seconds on Linux
  • Call Files.walk(..) on JVM
    • takes ~2.5 seconds on macOS
    • takes ~4 seconds on Windows
  • Would you wait several seconds for highlighting?

​

14 of 86

Full Text Search in IntelliJ

15 of 86

Trigram Index

“Swapper32”

Swa

wap

app

ppe

per

er3

r32

{

16 of 86

Trigram Index

“Swapper32”

Swa

wap

app

ppe

per

er3

r32

{

17 of 86

Trigram Index

“Swapper32”

Swa

wap

app

ppe

per

er3

r32

{

18 of 86

Trigram Index

“Swapper32”

Swa

wap

app

ppe

per

er3

r32

{

}

19 of 86

Trigram Index: Building

File -> List(Trigrams) /// building�Trigram -> List(File) /// using

Swa

wap

...

...

...

...

r32

{

20 of 86

Local Trigram Index Math

Local (inverted) Index:

Trigram -> List(File)

Swa

wap

...

...

...

...

r32

{

21 of 86

Local Index Formally

Local (inverted) Index:

Key -> List(File)

22 of 86

8m

23 of 86

9m

24 of 86

9m

25 of 86

9m

26 of 86

Class by Name Search

  • IntelliJ IDEA uses short class name indexes to show us the relevant information almost instantly

27 of 86

Find Usages

28 of 86

Find Usages Inside

Looking for the “Swapper32” identifier

  • Query the ID Index
    • The index of all identifiers of all languages
  • Process the list of files
    • Check every found “Swapper32” identifier to be valid
    • Use the “Go to declaration” (aka resolve) to test if the found identifier matches
    • Language specific indexes are used at that step too

29 of 86

Rename Refactoring

  • It collects all the usages of the symbol to be renamed
    • Uses Find Usages underneath
  • It changes the names at all places ensures the code is not broken
    • Add imports, reformat code, etc.

30 of 86

Indexes Are Used in IntelliJ

  • Find Usages
  • Navigation
  • Inspections
  • Highlighting (e.g. nullability checks in Java)
  • Full Text Search
  • Import popup
  • Refactorings
  • <almost everywhere>

31 of 86

How Many Indexes are There?

  • IntelliJ IDEA Ultimate
    • 208 different indexes
  • IntelliJ IDEA Community
    • 99 different indexes
  • The actual number of indexes depends on the plugins you have
    • My IntelliJ IDEA Ultimate uses only 155 indexes

32 of 86

Indexing can be slow

13m

33 of 86

Indexing is �done per IDE

14m

34 of 86

We spend human years per week on indexing

15m

35 of 86

Shared Indexes

15m

36 of 86

Shared Indexes

  • Replace local indexing with a pre-computed data
  • Make multiple IDE instances to use the same data
  • It uses special hash(File content) instead of a file
    • Local files may have different paths
      • c:\jonnyzzz\file.txt
      • /Users/jonnyzzz/file.txt
    • Local files may have different line-ends
    • Local files may be just different
      • different version control revisions
      • local changes

37 of 86

Shared Index Math (for one index)

Downloaded Shared Index:

Key -> List(Hash)

Local part for a Downloaded Shared Index:

File -> hash(File content)

Hash -> List(File)�

38 of 86

Shared Trigram Index Math

Trigram -> List(Hash) /// downloaded

File <- hash(File content) /// local

​

...

...

...

...

​

{

Shared

“Swapper32”

39 of 86

Combined Trigram Index Lookup

​

...

...

...

...

​

{

}

Local

Shared

“Swa”

40 of 86

Building a Trigram Shared Index

File -> hash(File content) -> List(Trigrams) /// building�Trigram -> List(Hash) /// using

Swa

wap

...

...

...

...

r32

{

41 of 86

It does not replace

​

​

Now,

Indexing completes faster

20m

42 of 86

Shared Indexes Allows to

  • use a shared index on another computer
    • a bundled shared index
    • a downloaded shared index
  • download a compatible shared index from the network
    • from public / provided by JetBrains CDN
    • on-premises location
    • the best suitable shared index is downloaded
  • build a shared index
    • for project or library
    • via a headless os-independent command line tool

43 of 86

Compatibility

  • We use IntelliJ codebase for the storage of shared indexes
  • Compatibility check is as follows:
    • The base version
      • must fully match
    • Per-index versions
      • should match to load the index
  • It is OK to use a partially compatible shared index
    • plugins change in the IDE
    • files changes on the disk
  • All missing entries are indexed locally

44 of 86

Public Shared Indexes

We build public shared indexes for the community:

  • For actual JDK releases
    • we use the same list of JDKs as for the JDK Downloader
  • For popular Maven libraries
    • a hard-coded list of popular libraries
  • For IntelliJ SDK based Gradle projects
    • we include the recent versions and EAPs
  • More to come!

45 of 86

Building Shared Indexes

  • Supported IntelliJ Versions
    • Releases from 2020.3
    • EAP builds of 2020.3 and 2021.1 (before expiration)
    • Nightly builds (for internal use)
  • Building
    • public shared indexes
    • internal shared indexes
      • for IntelliJ IDEA and other projects inside JetBrains
  • TeamCity runs our indexing tasks

46 of 86

Distributing Shared Indexes

  • IntelliJ uses a stateless protocol over HTTPS
    • to discover the best matching shared index
    • no need for the server-side logic
    • a downloaded shared index is cached at the IDE side
  • We have about 700Gb of data on the public CDN
    • constantly updating the data with newly build indexes
  • The world-wide shared indexes download service

47 of 86

Project Shared Indexes

  • The most generic application for the shared indexes
  • It helps to speed up indexing on various projects
    • Faster clean indexing time improvements
    • Faster branch switching
    • The actual performance improvement depends on the project, languages, network, ect.
      • do not trust me, trust your profiler
  • Every team member would spend less time on indexing
  • On-premises and cloud ready
  • Requires a custom setup
    • Stay tuned: we may have something cool to simplify that later this year

​

48 of 86

Project Shared Indexes Setup (Preview)

IntelliJ

Shared Indexes CDN

Shared Indexes�Job Runner

VCS

49 of 86

Experiments

31m

50 of 86

JDK Indexes

  • Built for every JDK from the JDK Downloader dialog
    • we use the common backend behind
    • Shared Indexes for a JDK are downloaded together with a JDK
  • The best matching JDK index is selected through
    • Using hash code of the JDK contents
    • Using JDK names and versions

​

51 of 86

JDK Index Example

Empty project with Amazon Corretto 11.0.9 on macOS

  • No Shared Index: 26. 703 s
  • With Shared Index: 16. 653 s

37% less time

52 of 86

Maven Libraries Shared Index

  • Generated by JetBrains for popular Maven libraries
    • Let me know if something is missing!
    • 123 libraries are listed now
  • Generated Especially for IntelliJ IDEA SDK
    • It includes all IntelliJ-Based IDEs done by JetBrains
  • Library index contains all transitive dependencies
  • IntelliJ matches the library by
    • by full name and version, e.g. “junit:junit:4.12”
    • by full name and major version, e.g. “junit:junit:4”

53 of 86

Maven Libraries Shared Index

Empty Gradle IntelliJ plugin project (or IJSDK) indexing on macOS:

  • No Shared Index: 141.889 s
  • With Shared Index: 50.383 s

64% less time

54 of 86

IntelliJ Community Project Example

The sources of all IntelliJ Community clean indexing time on macOS:

  • No Shared Index: 293.314 s
  • With Shared Index: 145.709 s

51% less time

​

​

IntelliJ Community project shared indexes are also included in the public shared indexes and configured for the project

55 of 86

IntelliJ Community with Shared Indexes

  • Event Log tells how many files index use shared indexes

56 of 86

IntelliJ Ultimate Project Example

The sources of all IntelliJ-based IDEs indexing time on macOS:

  • No Shared Index: 485.309 s
  • With Shared Index: 228.098 s

52% less time

57 of 86

Continuous measurements

37m

58 of 86

Continuous Measurements

  • Run same measurements
    • for all nightly IntelliJ builds
    • On the same hardware (Windows, Linux, Mac)
  • Measuring Shared Indexes
    • Build shared index locally
    • T1 = Indexing time with no shared indexes enabled
    • T2 = Indexing time with shared indexes
  • Well established continuous integration process
    • TeamCity

59 of 86

JDK Indexing time experimental data

60 of 86

IntelliJ Ultimate codebase indexing

61 of 86

Do not trust me,�Trust your profiler!

40m

62 of 86

What Affects the Results

  • Project specifics
    • Number of files, libraries, languages
  • Enabled plugins
  • Network Performance
    • Download of shared indexes time
    • Dependencies resolution time
  • Operating System
    • I/O performance

63 of 86

How can I try�shared indexes?

42m

64 of 86

You Are Using Bundled Shared Indexes

  • With IntelliJ IDEA Ultimate 2020.3+:
    • JavaScript
    • Go
  • With 2021.1+:
    • Python
    • PHP

65 of 86

Downloading Shared Indexes

  • For JDK and Maven libraries

66 of 86

Also check the Settings/Preferences

67 of 86

Downloadable Shared Indexes CDN Use

68 of 86

Try Project Shared Indexes

Follow the Guide: How To Try Shared Indexes

​

69 of 86

Shared Indexes in�IntelliJ Platform

47m

70 of 86

Shared Indexes Naming

  • 2020.3 and before
    • Shared Indexes plugin
      • bundled, downloadable, project shared indexes
  • 2021.1+
    • Shared Indexes Core is included into all JetBrains-made IDEs
      • bundled and public shared indexes download support
    • Project Shared Indexes plugin (preview)
      • the part for on-premisses project indexes support
      • shared indexes generation command

71 of 86

Shared Indexes: IntelliJ Community

  • 2020.3
    • Shared Indexes plugin
      • on the Marketplace (https://plugins.jetbrains.com)
  • 2021.1 (EAP)
    • Shared Indexes Core
      • included
    • Project Shared Indexes plugin (Preview)
      • on the Marketplace

72 of 86

Shared Indexes: IntelliJ Ultimate

  • 2020.3
    • Shared Indexes plugin
      • bundled
  • 2021.1 (EAP)
    • Shared Indexes Core
      • included
    • Project Shared Indexes plugin (Preview)
      • bundled

73 of 86

Shared Indexes: IntelliJ-based IDEs

  • 2020.3
    • Shared Indexes plugin:
      • bundled: WebStorm, PhpStorm, GoLand, IntelliJ IDEA Ultimate
      • on the Marketplace for other IJ-based IDEs
  • 2021.1 (EAP)
    • Shared Indexes Core
      • included to all IJ-based IDEs
      • also in IntelliJ IDEA Community & PyCharm Community
    • Project Shared Indexes plugin (Preview)
      • bundled in: 2020.3 + PyCharm
      • on the Marketplace for other JetBrains-made IDEs

74 of 86

Shared Indexes or �How we made�indexing complete faster

75 of 86

Q & A / Thanks!

twitter: @jonnyzzz / email: jo@jetbrains.com

76 of 86

twitter: @jonnyzzz / email: jo@jetbrains.com

Thanks!

77 of 86

// THE END

78 of 86

79 of 86

80 of 86

81 of 86

82 of 86

Shared Indexes for IntelliJ-based IDEs

  • In 2020.3:
    • Shared Indexes plugin
      • Bundled into IntelliJ IDEA Ultimate (and other IDEs)
      • Available on the Marketplace (for IJ-based IDEs)
  • In 2021.1 EAP:
    • Shared Indexes Core is embedded in IntelliJ-based IDE (built by JetBrains)
      • Bundled shared indexes
      • Downloadable shared indexes
    • Project Shared Indexes plugin is bundled in IntelliJ IDEA Ultimate (and other IDEs)
      • On-premises shared indexes for a project support (Preview)
      • Available on the Marketplace (for IJ-based IDEs)

83 of 86

How would IDE look for a symbol?

  • Say we need to find the “Swapper32” or “swap” method
  • It may do a text search first
  • Next it checks what role the string plays
    • it could be “a string constant Swapper32_64”
    • it could be “void Swapper32_method()”
    • or it could finally be a “class Swapper32” declaration
  • Only matching results are considered
  • Once found, an IDE may check if there is a “swap” method
    • with the right visibility, static/instance flags
    • with the right signature
  • Now the IDE may highlight the code appropriately
  • ​

84 of 86

GoLand

  • Bundled Indexes
  • Replacement for Prebuilt Stubs
  • 35% less time on empty project in comparison with prebuilt stubs

85 of 86

Attach the shared index

  • Use dump shared index action to generate an index
  • Remove IntelliJ System folder
  • Copy the generated index to the <system>/shared-index folder
  • Try indexing once again and measure time
  • More on how to set-up the process

86 of 86

Try Shared Indexes for Your Project