Re: RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow
+1 -Sundar On 16/10/17, 8:08 PM, Hannes Wallnöfer wrote: From my tests I concluded that leaving the queue threshold high as to not affect ‚ordinary‘ objects is the way to go. But it certainly doesn’t hurt to make the value configurable. I uploaded a new webrev that does this with a system property called „nashorn.propmap.queue.threshold“. It’s otherwise unchanged. http://cr.openjdk.java.net/~hannesw/8068513/webrev.03/ Hannes Am 16.10.2017 um 07:43 schrieb Sundararajan Athijegannathan: Is it worthwhile adding configurability for QUEUE_THREASHOLD? Not a per context property/option - but even a simple nashorn.* system property perhaps? +1 other than that -Sundar On 13/10/17, 7:55 PM, Hannes Wallnöfer wrote: I uploaded a new webrev, please review: http://cr.openjdk.java.net/~hannesw/8068513/webrev.02/ Changes to previous webrev: - updated to consolidated repository layout - fixed typos and improved/added some comments - improved test Thanks, Hannes Am 11.09.2017 um 16:18 schrieb Hannes Wallnöfer : Unfortunately I rushed the first webrev a bit, and a couple of bugs slipped in. - PropertyHashMap(MapBuilder) constructor checks its own bins field instead of MapBuilder’s for calculating threshold - ElementQueue.cloneAndMerge() updates the queue field in PropertyHashMap instead of just returning cloned and merged bins I uploaded a new webrev that fixes these problems, everything I wrote in my original RFR still applies. http://cr.openjdk.java.net/~hannesw/8068513/webrev.01/ Thanks, Hannes Am 05.09.2017 um 19:57 schrieb Hannes Wallnöfer : Please review 8068513: Adding elements to a javascript 'object' (a map) is slow: Bug: https://bugs.openjdk.java.net/browse/JDK-8068513 Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/ This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap that is used above a certain map size to store newly inserted elements without having to hash them (and therefore clone the bins array) immediately. Instead, The queue is merged into the hash bins at certain intervals, either every 512th insertions, or when a map's queue is searched for properties more than a few times. Merging the queue every 512 insertions proved to be the best balance between keeping the list searchable (we still need to check it for duplicates when adding elements) and avoiding too frequent cloning. In order to merge the queue to optimise query performance, the queue field needs to be non-final. To preserve thread safety, ElementQueue bundles both the bins and queue components, so it can replace both with the update of a single reference in PropertyHashMap. The old and new ElementQueue instances logically contain the same elements, so it is safe for other threads to keep using the old instance. I was thinking of maybe making the queue field volatile, but I don’t think this should be an issue. As part of this change I also added a new MapBuilder class that helps derive new maps from the existing ones by adding, replacing, or removing elements. The code is a bit more complex now with three possible storage data structures (list, bins, queue), but it’s still not too bad. I made sure that the code used for maps beneath the queue threshold is largely the same as before. Performance of the new combined behaveior is very close to before. The queued implementation itself performs pretty close to the normal implementation (apart from insertion on large maps of course) - I tested much lower thresholds during development, and it was still very good. Of course, all tests pass and performance is comparable or maybe slightly faster for some code. Thanks, Hannes
Re: RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow
From my tests I concluded that leaving the queue threshold high as to not affect ‚ordinary‘ objects is the way to go. But it certainly doesn’t hurt to make the value configurable. I uploaded a new webrev that does this with a system property called „nashorn.propmap.queue.threshold“. It’s otherwise unchanged. http://cr.openjdk.java.net/~hannesw/8068513/webrev.03/ Hannes > Am 16.10.2017 um 07:43 schrieb Sundararajan Athijegannathan >: > > Is it worthwhile adding configurability for QUEUE_THREASHOLD? Not a per > context property/option - but even a simple nashorn.* system property perhaps? > > +1 other than that > > -Sundar > > On 13/10/17, 7:55 PM, Hannes Wallnöfer wrote: >> I uploaded a new webrev, please review: >> >> http://cr.openjdk.java.net/~hannesw/8068513/webrev.02/ >> >> Changes to previous webrev: >> >> - updated to consolidated repository layout >> - fixed typos and improved/added some comments >> - improved test >> >> Thanks, >> Hannes >> >> >>> Am 11.09.2017 um 16:18 schrieb Hannes >>> Wallnöfer : >>> >>> Unfortunately I rushed the first webrev a bit, and a couple of bugs slipped >>> in. >>> >>> - PropertyHashMap(MapBuilder) constructor checks its own bins field >>> instead of MapBuilder’s for calculating threshold >>> - ElementQueue.cloneAndMerge() updates the queue field in PropertyHashMap >>> instead of just returning cloned and merged bins >>> >>> I uploaded a new webrev that fixes these problems, everything I wrote in my >>> original RFR still applies. >>> >>> http://cr.openjdk.java.net/~hannesw/8068513/webrev.01/ >>> >>> Thanks, >>> Hannes >>> >>> Am 05.09.2017 um 19:57 schrieb Hannes Wallnöfer : Please review 8068513: Adding elements to a javascript 'object' (a map) is slow: Bug: https://bugs.openjdk.java.net/browse/JDK-8068513 Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/ This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap that is used above a certain map size to store newly inserted elements without having to hash them (and therefore clone the bins array) immediately. Instead, The queue is merged into the hash bins at certain intervals, either every 512th insertions, or when a map's queue is searched for properties more than a few times. Merging the queue every 512 insertions proved to be the best balance between keeping the list searchable (we still need to check it for duplicates when adding elements) and avoiding too frequent cloning. In order to merge the queue to optimise query performance, the queue field needs to be non-final. To preserve thread safety, ElementQueue bundles both the bins and queue components, so it can replace both with the update of a single reference in PropertyHashMap. The old and new ElementQueue instances logically contain the same elements, so it is safe for other threads to keep using the old instance. I was thinking of maybe making the queue field volatile, but I don’t think this should be an issue. As part of this change I also added a new MapBuilder class that helps derive new maps from the existing ones by adding, replacing, or removing elements. The code is a bit more complex now with three possible storage data structures (list, bins, queue), but it’s still not too bad. I made sure that the code used for maps beneath the queue threshold is largely the same as before. Performance of the new combined behaveior is very close to before. The queued implementation itself performs pretty close to the normal implementation (apart from insertion on large maps of course) - I tested much lower thresholds during development, and it was still very good. Of course, all tests pass and performance is comparable or maybe slightly faster for some code. Thanks, Hannes
Re: RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow
Is it worthwhile adding configurability for QUEUE_THREASHOLD? Not a per context property/option - but even a simple nashorn.* system property perhaps? +1 other than that -Sundar On 13/10/17, 7:55 PM, Hannes Wallnöfer wrote: I uploaded a new webrev, please review: http://cr.openjdk.java.net/~hannesw/8068513/webrev.02/ Changes to previous webrev: - updated to consolidated repository layout - fixed typos and improved/added some comments - improved test Thanks, Hannes Am 11.09.2017 um 16:18 schrieb Hannes Wallnöfer: Unfortunately I rushed the first webrev a bit, and a couple of bugs slipped in. - PropertyHashMap(MapBuilder) constructor checks its own bins field instead of MapBuilder’s for calculating threshold - ElementQueue.cloneAndMerge() updates the queue field in PropertyHashMap instead of just returning cloned and merged bins I uploaded a new webrev that fixes these problems, everything I wrote in my original RFR still applies. http://cr.openjdk.java.net/~hannesw/8068513/webrev.01/ Thanks, Hannes Am 05.09.2017 um 19:57 schrieb Hannes Wallnöfer : Please review 8068513: Adding elements to a javascript 'object' (a map) is slow: Bug: https://bugs.openjdk.java.net/browse/JDK-8068513 Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/ This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap that is used above a certain map size to store newly inserted elements without having to hash them (and therefore clone the bins array) immediately. Instead, The queue is merged into the hash bins at certain intervals, either every 512th insertions, or when a map's queue is searched for properties more than a few times. Merging the queue every 512 insertions proved to be the best balance between keeping the list searchable (we still need to check it for duplicates when adding elements) and avoiding too frequent cloning. In order to merge the queue to optimise query performance, the queue field needs to be non-final. To preserve thread safety, ElementQueue bundles both the bins and queue components, so it can replace both with the update of a single reference in PropertyHashMap. The old and new ElementQueue instances logically contain the same elements, so it is safe for other threads to keep using the old instance. I was thinking of maybe making the queue field volatile, but I don’t think this should be an issue. As part of this change I also added a new MapBuilder class that helps derive new maps from the existing ones by adding, replacing, or removing elements. The code is a bit more complex now with three possible storage data structures (list, bins, queue), but it’s still not too bad. I made sure that the code used for maps beneath the queue threshold is largely the same as before. Performance of the new combined behaveior is very close to before. The queued implementation itself performs pretty close to the normal implementation (apart from insertion on large maps of course) - I tested much lower thresholds during development, and it was still very good. Of course, all tests pass and performance is comparable or maybe slightly faster for some code. Thanks, Hannes
Re: RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow
+1 > On Oct 13, 2017, at 11:25 AM, Hannes Wallnöfer> wrote: > > I uploaded a new webrev, please review: > > http://cr.openjdk.java.net/~hannesw/8068513/webrev.02/ > > Changes to previous webrev: > > - updated to consolidated repository layout > - fixed typos and improved/added some comments > - improved test > > Thanks, > Hannes > > >> Am 11.09.2017 um 16:18 schrieb Hannes Wallnöfer >> : >> >> Unfortunately I rushed the first webrev a bit, and a couple of bugs slipped >> in. >> >> - PropertyHashMap(MapBuilder) constructor checks its own bins field instead >> of MapBuilder’s for calculating threshold >> - ElementQueue.cloneAndMerge() updates the queue field in PropertyHashMap >> instead of just returning cloned and merged bins >> >> I uploaded a new webrev that fixes these problems, everything I wrote in my >> original RFR still applies. >> >> http://cr.openjdk.java.net/~hannesw/8068513/webrev.01/ >> >> Thanks, >> Hannes >> >> >>> Am 05.09.2017 um 19:57 schrieb Hannes Wallnöfer >>> : >>> >>> Please review 8068513: Adding elements to a javascript 'object' (a map) is >>> slow: >>> >>> Bug: https://bugs.openjdk.java.net/browse/JDK-8068513 >>> Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/ >>> >>> This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap >>> that is used above a certain map size to store newly inserted elements >>> without having to hash them (and therefore clone the bins array) >>> immediately. Instead, The queue is merged into the hash bins at certain >>> intervals, either every 512th insertions, or when a map's queue is searched >>> for properties more than a few times. >>> >>> Merging the queue every 512 insertions proved to be the best balance >>> between keeping the list searchable (we still need to check it for >>> duplicates when adding elements) and avoiding too frequent cloning. >>> >>> In order to merge the queue to optimise query performance, the queue field >>> needs to be non-final. To preserve thread safety, ElementQueue bundles both >>> the bins and queue components, so it can replace both with the update of a >>> single reference in PropertyHashMap. The old and new ElementQueue instances >>> logically contain the same elements, so it is safe for other threads to >>> keep using the old instance. I was thinking of maybe making the queue field >>> volatile, but I don’t think this should be an issue. >>> >>> As part of this change I also added a new MapBuilder class that helps >>> derive new maps from the existing ones by adding, replacing, or removing >>> elements. The code is a bit more complex now with three possible storage >>> data structures (list, bins, queue), but it’s still not too bad. >>> >>> I made sure that the code used for maps beneath the queue threshold is >>> largely the same as before. Performance of the new combined behaveior is >>> very close to before. The queued implementation itself performs pretty >>> close to the normal implementation (apart from insertion on large maps of >>> course) - I tested much lower thresholds during development, and it was >>> still very good. >>> >>> Of course, all tests pass and performance is comparable or maybe slightly >>> faster for some code. >>> >>> Thanks, >>> Hannes >> >
Re: RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow
I uploaded a new webrev, please review: http://cr.openjdk.java.net/~hannesw/8068513/webrev.02/ Changes to previous webrev: - updated to consolidated repository layout - fixed typos and improved/added some comments - improved test Thanks, Hannes > Am 11.09.2017 um 16:18 schrieb Hannes Wallnöfer >: > > Unfortunately I rushed the first webrev a bit, and a couple of bugs slipped > in. > > - PropertyHashMap(MapBuilder) constructor checks its own bins field instead > of MapBuilder’s for calculating threshold > - ElementQueue.cloneAndMerge() updates the queue field in PropertyHashMap > instead of just returning cloned and merged bins > > I uploaded a new webrev that fixes these problems, everything I wrote in my > original RFR still applies. > > http://cr.openjdk.java.net/~hannesw/8068513/webrev.01/ > > Thanks, > Hannes > > >> Am 05.09.2017 um 19:57 schrieb Hannes Wallnöfer >> : >> >> Please review 8068513: Adding elements to a javascript 'object' (a map) is >> slow: >> >> Bug: https://bugs.openjdk.java.net/browse/JDK-8068513 >> Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/ >> >> This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap >> that is used above a certain map size to store newly inserted elements >> without having to hash them (and therefore clone the bins array) >> immediately. Instead, The queue is merged into the hash bins at certain >> intervals, either every 512th insertions, or when a map's queue is searched >> for properties more than a few times. >> >> Merging the queue every 512 insertions proved to be the best balance between >> keeping the list searchable (we still need to check it for duplicates when >> adding elements) and avoiding too frequent cloning. >> >> In order to merge the queue to optimise query performance, the queue field >> needs to be non-final. To preserve thread safety, ElementQueue bundles both >> the bins and queue components, so it can replace both with the update of a >> single reference in PropertyHashMap. The old and new ElementQueue instances >> logically contain the same elements, so it is safe for other threads to keep >> using the old instance. I was thinking of maybe making the queue field >> volatile, but I don’t think this should be an issue. >> >> As part of this change I also added a new MapBuilder class that helps derive >> new maps from the existing ones by adding, replacing, or removing elements. >> The code is a bit more complex now with three possible storage data >> structures (list, bins, queue), but it’s still not too bad. >> >> I made sure that the code used for maps beneath the queue threshold is >> largely the same as before. Performance of the new combined behaveior is >> very close to before. The queued implementation itself performs pretty close >> to the normal implementation (apart from insertion on large maps of course) >> - I tested much lower thresholds during development, and it was still very >> good. >> >> Of course, all tests pass and performance is comparable or maybe slightly >> faster for some code. >> >> Thanks, >> Hannes >
Re: RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow
Unfortunately I rushed the first webrev a bit, and a couple of bugs slipped in. - PropertyHashMap(MapBuilder) constructor checks its own bins field instead of MapBuilder’s for calculating threshold - ElementQueue.cloneAndMerge() updates the queue field in PropertyHashMap instead of just returning cloned and merged bins I uploaded a new webrev that fixes these problems, everything I wrote in my original RFR still applies. http://cr.openjdk.java.net/~hannesw/8068513/webrev.01/ Thanks, Hannes > Am 05.09.2017 um 19:57 schrieb Hannes Wallnöfer >: > > Please review 8068513: Adding elements to a javascript 'object' (a map) is > slow: > > Bug: https://bugs.openjdk.java.net/browse/JDK-8068513 > Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/ > > This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap > that is used above a certain map size to store newly inserted elements > without having to hash them (and therefore clone the bins array) immediately. > Instead, The queue is merged into the hash bins at certain intervals, either > every 512th insertions, or when a map's queue is searched for properties more > than a few times. > > Merging the queue every 512 insertions proved to be the best balance between > keeping the list searchable (we still need to check it for duplicates when > adding elements) and avoiding too frequent cloning. > > In order to merge the queue to optimise query performance, the queue field > needs to be non-final. To preserve thread safety, ElementQueue bundles both > the bins and queue components, so it can replace both with the update of a > single reference in PropertyHashMap. The old and new ElementQueue instances > logically contain the same elements, so it is safe for other threads to keep > using the old instance. I was thinking of maybe making the queue field > volatile, but I don’t think this should be an issue. > > As part of this change I also added a new MapBuilder class that helps derive > new maps from the existing ones by adding, replacing, or removing elements. > The code is a bit more complex now with three possible storage data > structures (list, bins, queue), but it’s still not too bad. > > I made sure that the code used for maps beneath the queue threshold is > largely the same as before. Performance of the new combined behaveior is very > close to before. The queued implementation itself performs pretty close to > the normal implementation (apart from insertion on large maps of course) - I > tested much lower thresholds during development, and it was still very good. > > Of course, all tests pass and performance is comparable or maybe slightly > faster for some code. > > Thanks, > Hannes
RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow
Please review 8068513: Adding elements to a javascript 'object' (a map) is slow: Bug: https://bugs.openjdk.java.net/browse/JDK-8068513 Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/ This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap that is used above a certain map size to store newly inserted elements without having to hash them (and therefore clone the bins array) immediately. Instead, The queue is merged into the hash bins at certain intervals, either every 512th insertions, or when a map's queue is searched for properties more than a few times. Merging the queue every 512 insertions proved to be the best balance between keeping the list searchable (we still need to check it for duplicates when adding elements) and avoiding too frequent cloning. In order to merge the queue to optimise query performance, the queue field needs to be non-final. To preserve thread safety, ElementQueue bundles both the bins and queue components, so it can replace both with the update of a single reference in PropertyHashMap. The old and new ElementQueue instances logically contain the same elements, so it is safe for other threads to keep using the old instance. I was thinking of maybe making the queue field volatile, but I don’t think this should be an issue. As part of this change I also added a new MapBuilder class that helps derive new maps from the existing ones by adding, replacing, or removing elements. The code is a bit more complex now with three possible storage data structures (list, bins, queue), but it’s still not too bad. I made sure that the code used for maps beneath the queue threshold is largely the same as before. Performance of the new combined behaveior is very close to before. The queued implementation itself performs pretty close to the normal implementation (apart from insertion on large maps of course) - I tested much lower thresholds during development, and it was still very good. Of course, all tests pass and performance is comparable or maybe slightly faster for some code. Thanks, Hannes