RFR JDK-8059510 Compact symbol table layout inside shared archive
jiangli.zhou at oracle.com
Tue Dec 2 21:44:45 UTC 2014
I finally got back to this, sorry for the delay. Please see the
following new webre.
New in the webrev:
1. Further compression of the compact table
* Remove the bucket_size table. With the sequential layout of the
buckets, lookup process can seek to the start of the next bucket
without the need of the current bucket size. For the last bucket, it
can seek to the end of the table. The table end offset is added to
the archived data.
* Bucket with exactly one entry is marked as 'compact' bucket, whose
entry only contains the symbol offset. The symbol hash is eliminated
for 'compact' buckets. Lookup compares the symbol directly in that case.
2. The shared symbol table is not always looked up first. The last table
that fetches symbol successfully is used for lookup.
3. Added a lot more comments in compactHashtable.hpp with details of the
compact table layout and dump/lookup process.
I measured using the classloading benchmark that Aleksey pointed to me.
This benchmark loads classes using user defined classloader. There is a
very small degradation shown in the benchmark comparing 'before' and
'after' with archive dumped with the default configuration. When symbols
from the test is added to the shared table, there is an observable
speedup in the benchmark. The speedup is also very small.
On 10/29/2014 02:55 PM, Jiangli Zhou wrote:
> Hi John,
> Thank you for the thoughts on this! Yes, it's a good time to have
> these conversations. Please see some quick responses from me below,
> with more details to follow.
> On 10/29/2014 12:46 PM, John Rose wrote:
>> I have a few points about the impact of this change on startup performance, and on trends in our code base:
>> 1. We can live with small performance regressions on some benchmarks. Otherwise we'd never get anywhere. So I am not saying that the current (very interesting and multi-facted) conversation must continue a long time before we can push any code.
>> 2. Aleksey's challenge is valid, and I don't see a strong reply to it yet. Work like this, that emphasizes compactness and sharability can usually be given the benefit of the doubt for startup. But if we observe a problem we should make a more careful measurement. If this change goes in with a measurable regression, we need a follow-up conversation (centered around a tracking bug) about quantifying the performance regression and fixing it. (It's possible the conversation ends by saying "we decided we don't care and here's why", but I doubt it will end that way.)
> Besides my classloading benchmark results posted in earlier message,
> we have asked performance team to help us measure startup,
> classloding, and memory saving regarding this change, and verified
> there was no regression in startup/classloading. The results were not
> posted in the thread however. They were added to the bug report for
> JDK-8059510 <https://bugs.openjdk.java.net/browse/JDK-8059510>.
>> 3. The benchmark Aleksey chose, Nashorn startup, may well be an outlier. Dynamic language runtimes create lots of tiny methods, and are likely to put heavy loads on symbol resolution, including resolution of symbols that are not known statically. For these, the first-look (front-end) table being proposed might be a loss, especially if the Nashorn runtime is not in the first-look table.
>> 4. Possible workarounds: #1 Track hit rates and start looking at the static table *second* if it fails to produce enough hits, compared to the dynamic table. #2 When that happens, incrementally migrate (rehash) frequently found symbols in the static table into the main table. #3 Re-evaluate the hashing algorithm. (More on this below.)
> That's interesting thinking. I'll follow up on this.
>> 5. I strongly support moving towards position-independent, shareable, pointer-free data structures, and I want us to learn to do it well over time. (Ioi, you are one of our main explorers here!) To me, a performance regression is a suggestion that we have something more to learn. And, it's not a surprise that we don't have it all figured out yet.
> Point taken! Position-independent is one of our goal for the archived
> data. We'll be start looking into removing direct pointers in the
> shared class data.
>> 6. For work like this, we need to agree upon at least one or two startup performance tests to shake out bottlenecks early and give confidence. People who work on startup performance should know how to run them and be able to quote them.
> Thank you for bring this up. Totally agree. For me, personally I've
> played with different benchmarks and applications with different focus
> over time. It would be good to have some commonly agreed startup
> performance tests for this. A standalone classloading benchmark,
> HelloWorld and Nashorn startup probably are good choices. We also have
> an internal application for startup and memory saving measurement.
>> 7. There's a vibrant literature about offline (statically created) hash tables, and lots of tricks floating around, such as perfect or semi-perfect hash functions, and multiple-choice hashing, and locality-aware structures. I can think of several algorithmic tweaks I'd like to try on this code. (If they haven't already been tried or discarded: I assume Ioi has already tried a number of things.) Moreover, this is not just doorknob-polishing, because (as said in point 5) we want to develop our competency with these sorts of data structures.
>> 8. I found the code hard to read, so it was hard to reason about the algorithm. The core routine, "lookup", has no comments and only one assert. It uses only primitive C types and (perhaps in the name of performance) is not factored into sub-functions. The code which generates the static table is also hard to reason about in similar ways. The bucket size parameter choice (a crucial compromise between performance and compactness) is 4 but the motivation and implications are left for the reader to puzzle out. Likewise, the use of hardware division instead of power-of-two table size is presented without comment, despite the fact that we favor power-of-two in other parts of our stack, and a power-of-two solution would be reasonable here (given the bucket size).
>> 9. Perhaps I wouldn't care as much about the code style if the code were not performance sensitive or if it were a unique and isolated part of the JVM. In this case, I expect this code (and other similar code) to improve, over time, in readability and robustness, as we learn to work with this new kind of data structure. So even if we decide there is no significant regression here, and decide to push it as-is, we still need to use it as an example to help us get better at writing easy-to-read code which works with pointer-free data.
>> 10. I would like to see (posted somewhere or attached to the bug) a sample list of the symbols in a typical symbol table. Perhaps this already exists and I missed it. I think it would be friendly to put some comments in the code that help the reader estimate numbers like table size, bucket length, number of queries, number of probes per query, symbol length statistics (mean, histogram). Of course such comments go stale over time, but so does the algorithm, and being coy about the conditions of the moment doesn't help us in the long run. Even a short comment is better than none, for example:
> Those are good suggestions. I'll add a sample list o the symbols to
> the bug report and try to put more comments in the code.
>> It is a good time to have these conversations.
>> Best wishes,
>> — John
>> On Oct 13, 2014, at 11:46 AM, Aleksey Shipilev<aleksey.shipilev at oracle.com> wrote:
>>> Hi Jiangli,
>>> On 13.10.2014 18:26, Jiangli Zhou wrote:
>>>> On 10/13/2014 03:18 AM, Aleksey Shipilev wrote:
>>>>> On 13.10.2014 03:32, David Holmes wrote:
>>>>>> On 11/10/2014 1:47 PM, Jiangli Zhou wrote:
>>>>>> Also is the benchmarking being done on dedicated systems?
>>>>> Also, specjvm98 is meaningless to estimate the classloading costs.
>>>>> Please try specjvm2008:startup.* tests?
>>>> The specjvm run was for Gerard's question about standard benchmarks.
>>> SPECjvm2008 is a standard benchmark. In fact, it is a benchmark that
>>> deprecates SPECjvm98.
>>>> These are not benchmarks specifically for classloading.
>>> There are benchmarks that try to estimate the startup costs.
>>> SPECjvm2008:startup.* tests are one of them.
>>>> However, I agree it's a good idea to run standard benchmarks to
>>>> confirm there is no overall performance degradation. From all the
>>>> benchmarks including classloading measurements, we have confirmed
>>>> that this specific change does not have negative impact on
>>>> classloading itself and the overall performance.
>>> Excellent. What are those benchmarks? May we see those? Because I have a
>>> counter-example in this thread that this change *does* negatively impact
More information about the hotspot-runtime-dev