apache / apache/jena

PrefixMapStd is very slow for lookups that 'miss'

Open
#1,474 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Java
Stars
1.4k
Forks
712
Avg merge
15h 41m
Merged PRs (30d)
53

Description

PR: https://github.com/apache/jena/pull/1475

### Version

4.6.0-SNAPSHOT

### What happened?

Another follow up on https://issues.apache.org/jira/browse/JENA-2309
I investigated the issue of slow PrefixMapStd further and it turns out that when there are 'hits' using its fast track approach it's very fast - however on 'misses' it gets extremely slow because then it falls back to iteration of all prefixes in the map.

Using a small benchmark runner (part of the PR - [see here](https://github.com/apache/jena/pull/1475/files#diff-cc1bbc6e97e9accf2a8c4ad587a1b8bfebe38c9474827ef2761069d6b6a4b93dR236)) shows the the PrefixMapStd can be easily brought to require dozens of seconds for lookups that can actually be accomplished in a split second.
For that I created a new PrefixMap intended as a replacement that combines the best of both worlds: The fast track of PrefixMapStd and the trie backing (together with a guava cache) of the removed FastAbbreviatingPrefixMap.

Approach 0 = Jena's original PrefixMapStd:
```
Run 1 with base and separator / using approach 0: Static IRI lookups took 0.082 seconds
Run 1 with base and separator / using approach 0: Dynamic IRI lookups took 33.443 seconds
Run 1 with base and separator : using approach 0: Static IRI lookups took 25.482 seconds
Run 1 with base and separator : using approach 0: Dynamic IRI lookups took 31.088 seconds
```

Approach 1 = my optimized PrefixMap:
```
Run 1 with base and separator / using approach 1: Static IRI lookups took 0.070 seconds
Run 1 with base and separator / using approach 1: Dynamic IRI lookups took 0.401 seconds
Run 1 with base and separator : using approach 1: Static IRI lookups took 0.099 seconds
Run 1 with base and separator : using approach 1: Dynamic IRI lookups took 0.433 seconds
```

W.r.t. to the interface contract of PrefixMap I am not sure whether synchronization / thread-safe maps need to be used.
PrefixMapStd used a ConcurrentHashMap but if synchronization is actually not a concern then a LinkedHashMap that gives control over the order may be a better choice.

### Are you interested in making a pull request?

Yes

Contributor guide

Open the contributing guide

Research direction

Start by reading PrefixMapStd and the PrefixMap interface, then run the benchmark runner described in PR 1475. Done means prefix lookups that miss no longer fall back to iterating every prefix and show the improved timings reported for the optimized PrefixMap approach.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.