]> source.dussan.org Git - jgit.git/commit
Sort Config entries and use O(log N) lookup 86/5486/1
authorShawn O. Pearce <spearce@spearce.org>
Tue, 27 Mar 2012 15:49:13 +0000 (11:49 -0400)
committerShawn O. Pearce <spearce@spearce.org>
Tue, 27 Mar 2012 18:23:36 +0000 (14:23 -0400)
commit552682dc6aa8f3a77fac9a2d25a20914fcc65ba0
tree6325cce20d0195083877292748264341c03729ad
parent581e6ca2fe6f5d7c6a65b69a1dcf479c41fffbf2
Sort Config entries and use O(log N) lookup

Decrease running time for getStringList (and all other get methods) by
looking for configuration entries using binary search rather than
linear search through the configuration file.

Configuration lines are sorted by section, subsection, name in a
sorted list whenever the snapshot is rebuilt. Binary search is used to
locate an index in the middle of the values, then walk backwards to
find the first value in the range.

Given a configuration of file of 5000 distinct section/subsection/name
triplets (e.g. a Gerrit Code Review project.config configuration file
with 5000 unique access control rules), this new code is faster to
lookup each rule individually using getStringList():

  old setStringList() 194 usec avg
      getStringList() 196 usec avg

  new setStringList() 188 usec avg
      getStringList()  24 usec avg

Change-Id: Ic8907231868c18eb946b72f341a6b58666b70324
org.eclipse.jgit/src/org/eclipse/jgit/lib/Config.java
org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigSnapshot.java
org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java