Use 'char' instead of 'Character'

[knutwannheden]

There are a few classes and interfaces which declare methods with Character parameters or return types. Examples are NodeCharacterProvider#getIncomingEdgeFirstCharacter(), Node#getOutgoingEdge(), and NodeUtil#binarySearchForEdge().

But it seems like in the character value always originates as a char. Typically resulting as a call to CharSequence#charAt().

Particularly Node#getOutgoingEdge() is called a lot. So there would at least be a little bit to gain by declaring the parameters and return types as char instead, as the JVM wouldn't always have to autobox anymore.

I am however a bit unclear about the backwards compatibility requirements in this project. In the previous release there were methods added to RadixTree, which will have broken any client projects providing their own implementation (not subclassing ConcurrentRadixTree), even though there was only an increment in the minor version. I assume that is because most clients will only "use" the APIs and should thus remain compatible.

[npgall]

Hi Knut,

This is a good question. Currently Character is used (IIRC), to simplify the implementation of binary search in nodes, as it is convenient that it implements java.lang.Comparable.

AFAIK the auto-boxing of chars in Java, internally relies on Character.valueOf(char), which in turn uses a cache, so that the same Character object will be returned each time avoiding the creation of new Character objects. However, this cache is only used for ASCII characters. So although the main issue (unnecessary auto-boxing) won't apply to ASCII characters, it might apply to other characters...

Coincidentally I spoke to some JVM HotSpot/JIT and GC experts at a conference recently (with regard to this issue) about how smart HotSpot's escape analysis and inlining would be, in possibly eliminating the unnecessary auto-boxing that occurs here. The outcome was there is some support for "autobox elimination" in HotSpot, but the applicability to this situation was inconclusive. HotSpot might avoid the auto-boxing here, but it's not definitive.

So I'll try to test this. Thanks for this suggestion, it's definitely something worth investigating.

[knutwannheden]

I wouldn't be very surprised if the HotSpot compiler would be able to eliminate the auto-boxing here. But it certainly sounds quite complex with the Character objects being passed between multiple methods in different classes.

I gather that you are less concerned about introducing incompatibilities in the SPI (classes implementing interfaces like Node and NodeFactory) as opposed to the API (interfaces like RadixTree). But if the performance gains are minimal only, then I suppose it isn't worth it. I will also see if I can run some tests and report back the results.

[npgall]

Looks like there's some info about HotSpot's elimination of auto-boxing here, in quite a similar scenario: https://tavianator.com/java-autoboxing-performance/

It still needs more investigation though!

[knutwannheden]

I ran a simple performance test and there using char throughout was only marginally faster for purely ASCII keys (around 3%). With purely non-ASCII keys the difference was a bit bigger (15%).

My test created an "unbalanced" tree like this:

    RadixTree<Integer> tree = new ConcurrentRadixTree<Integer>(new DefaultCharArrayNodeFactory());
    StringBuilder key = new StringBuilder();
    for (int i = 0; i < 1000; i++) {
        char c = 'a';
        key.append(c);
        tree.put(key, i % 100);
        tree.put(key.toString() + (c + 1), i % 100);
    }

and then I did a series of lookups using the key represented by key at the end of this loop. I didn't use JMH and I didn't look at any of the compiled assembler code.

As for the reason to use Character: If char were used instead you would of course just do a a - b instead of an a.compareTo(b) for the binary search 😃

[npgall]

Interesting. I think the case where performance improves by 3% with ASCII characters, is probably because Character objects are not being created at all in that case: they are being returned from the cache. I'd guess the 3% overhead is probably due to the unboxing which is still required.

I think that the 15% performance improvement in the case with non-ASCII characters, is probably because new Character objects were being created every time. So it creates more garbage AND there will still be the unboxing overhead as well.

Maybe both of these issues could be eliminated if I replaced the auto-boxing which exists now, with explicit boxing, as discussed in the article I linked above. This may allow HotSpot to eliminate the boxing entirely. It would also not require any API changes.

On the other hand, this problem seems to be caused by a strange weakness in HotSpot - where it's less efficient at optimizing auto-boxing than it is at optimizing explicit boxing.