src/model/model_index: model index uses BKTree

nitlang / nit

Nit language

http://nitlanguage.org

Apache License 2.0

242 stars 67 forks source link

src/model/model_index: model index uses BKTree #2724

Closed Morriar closed 6 years ago

Morriar commented 6 years ago

This PR makes ModelIndex use a BKTree (#2718) to speed up Nitweb name similarity search queries on large code corpora.

Levenstein names comparison with 300k+ entities took a bit long (up to 10s for Nitweb with contrib and src for some queries). The use of BKTree speeds things up and brings those queries under 0.1s.

privat commented 6 years ago

@Morriar can you fix conflicts?

privat commented 6 years ago

I tried a merge in https://github.com/privat/mynit/commit/model-index let's see if it is ok. Note that github is crap at showing a combined diff (more than one parent)

Morriar commented 6 years ago

@privat I rebased on master, waiting for Jenkins.