You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@qpid.apache.org by Gordon Sim <gs...@redhat.com> on 2015/05/01 11:59:40 UTC
Review Request 33750: Optimisation of map entry deletion
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/33750/
-----------------------------------------------------------
Review request for qpid, Alan Conway, Andrew Stitcher, and Rafael Schloming.
Repository: qpid-proton-git
Description
-------
This implements the optimisation suggested by Alan. If the next entry in a chain after the one being deleted is in the cellar (i.e. is non-addressable), then there is no need to rehahs, that next entry can simply be copied into the slot being deleted,and the next slot can be freed.
Diffs
-----
proton-c/src/object/map.c 2e3b157
Diff: https://reviews.apache.org/r/33750/diff/
Testing
-------
The second unit test covers this case (as well as some others). My stress testing has also shown no issue with it.
Thanks,
Gordon Sim
Re: Review Request 33750: Optimisation of map entry deletion
Posted by Alan Conway <ac...@redhat.com>.
> On May 1, 2015, 11:11 a.m., Rafael Schloming wrote:
> > I have mixed feelings about this sort of change in general. I don't like making the code more complicated without some evidence that it will have a measurable impact, particularly with code that is already quite dense and subtle such as this. Do we have more than just conjecture in this case, e.g. is this a well known technique, or have we measured the effect?
> >
> > It's plausible to suggest that the benefit of this change may be limited since the resizing heuristics that control the load factor of the map will be working against the likelyhood of it ever triggering. I also suspect that soft deletes along with amortized rehashing would yield a much better optimization and render this one all but inert.
Conjecture by me. Do we have any performance benchmarks that could measure the impact of changes like this?
- Alan
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/33750/#review82242
-----------------------------------------------------------
On May 1, 2015, 9:59 a.m., Gordon Sim wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/33750/
> -----------------------------------------------------------
>
> (Updated May 1, 2015, 9:59 a.m.)
>
>
> Review request for qpid, Alan Conway, Andrew Stitcher, and Rafael Schloming.
>
>
> Repository: qpid-proton-git
>
>
> Description
> -------
>
> This implements the optimisation suggested by Alan. If the next entry in a chain after the one being deleted is in the cellar (i.e. is non-addressable), then there is no need to rehahs, that next entry can simply be copied into the slot being deleted,and the next slot can be freed.
>
>
> Diffs
> -----
>
> proton-c/src/object/map.c 2e3b157
>
> Diff: https://reviews.apache.org/r/33750/diff/
>
>
> Testing
> -------
>
> The second unit test covers this case (as well as some others). My stress testing has also shown no issue with it.
>
>
> Thanks,
>
> Gordon Sim
>
>
Re: Review Request 33750: Optimisation of map entry deletion
Posted by Rafael Schloming <rh...@apache.org>.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/33750/#review82242
-----------------------------------------------------------
I have mixed feelings about this sort of change in general. I don't like making the code more complicated without some evidence that it will have a measurable impact, particularly with code that is already quite dense and subtle such as this. Do we have more than just conjecture in this case, e.g. is this a well known technique, or have we measured the effect?
It's plausible to suggest that the benefit of this change may be limited since the resizing heuristics that control the load factor of the map will be working against the likelyhood of it ever triggering. I also suspect that soft deletes along with amortized rehashing would yield a much better optimization and render this one all but inert.
- Rafael Schloming
On May 1, 2015, 9:59 a.m., Gordon Sim wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/33750/
> -----------------------------------------------------------
>
> (Updated May 1, 2015, 9:59 a.m.)
>
>
> Review request for qpid, Alan Conway, Andrew Stitcher, and Rafael Schloming.
>
>
> Repository: qpid-proton-git
>
>
> Description
> -------
>
> This implements the optimisation suggested by Alan. If the next entry in a chain after the one being deleted is in the cellar (i.e. is non-addressable), then there is no need to rehahs, that next entry can simply be copied into the slot being deleted,and the next slot can be freed.
>
>
> Diffs
> -----
>
> proton-c/src/object/map.c 2e3b157
>
> Diff: https://reviews.apache.org/r/33750/diff/
>
>
> Testing
> -------
>
> The second unit test covers this case (as well as some others). My stress testing has also shown no issue with it.
>
>
> Thanks,
>
> Gordon Sim
>
>
Re: Review Request 33750: Optimisation of map entry deletion
Posted by Alan Conway <ac...@redhat.com>.
> On May 1, 2015, 1:29 p.m., Andrew Stitcher wrote:
> > I see nothing wrong with the code.
> >
> > However I do tend to agree with Rafi that this makes the code more complex and even less easy to understand then it already was.
> >
> > A big help would be a block comment describing the implementation at the top of the file with text diagrams etc.
> >
> > Perhaps more important would be a description somewhere of the data structure invariants.
>
> Alan Conway wrote:
> +1, to save time I'd suggest a comment pointing to http://en.wikipedia.org/wiki/Coalesced_hashing - then you only have to describe how this implementation differs, where the "cellar" is etc. rather than writing a paper on coalesced hashing
Note that the wiki article points out that deletion and resizing can be "difficult" in coalesced hashing. It's not just us ;)
- Alan
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/33750/#review82247
-----------------------------------------------------------
On May 1, 2015, 9:59 a.m., Gordon Sim wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/33750/
> -----------------------------------------------------------
>
> (Updated May 1, 2015, 9:59 a.m.)
>
>
> Review request for qpid, Alan Conway, Andrew Stitcher, and Rafael Schloming.
>
>
> Repository: qpid-proton-git
>
>
> Description
> -------
>
> This implements the optimisation suggested by Alan. If the next entry in a chain after the one being deleted is in the cellar (i.e. is non-addressable), then there is no need to rehahs, that next entry can simply be copied into the slot being deleted,and the next slot can be freed.
>
>
> Diffs
> -----
>
> proton-c/src/object/map.c 2e3b157
>
> Diff: https://reviews.apache.org/r/33750/diff/
>
>
> Testing
> -------
>
> The second unit test covers this case (as well as some others). My stress testing has also shown no issue with it.
>
>
> Thanks,
>
> Gordon Sim
>
>
Re: Review Request 33750: Optimisation of map entry deletion
Posted by Alan Conway <ac...@redhat.com>.
> On May 1, 2015, 1:29 p.m., Andrew Stitcher wrote:
> > I see nothing wrong with the code.
> >
> > However I do tend to agree with Rafi that this makes the code more complex and even less easy to understand then it already was.
> >
> > A big help would be a block comment describing the implementation at the top of the file with text diagrams etc.
> >
> > Perhaps more important would be a description somewhere of the data structure invariants.
+1, to save time I'd suggest a comment pointing to http://en.wikipedia.org/wiki/Coalesced_hashing - then you only have to describe how this implementation differs, where the "cellar" is etc. rather than writing a paper on coalesced hashing
- Alan
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/33750/#review82247
-----------------------------------------------------------
On May 1, 2015, 9:59 a.m., Gordon Sim wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/33750/
> -----------------------------------------------------------
>
> (Updated May 1, 2015, 9:59 a.m.)
>
>
> Review request for qpid, Alan Conway, Andrew Stitcher, and Rafael Schloming.
>
>
> Repository: qpid-proton-git
>
>
> Description
> -------
>
> This implements the optimisation suggested by Alan. If the next entry in a chain after the one being deleted is in the cellar (i.e. is non-addressable), then there is no need to rehahs, that next entry can simply be copied into the slot being deleted,and the next slot can be freed.
>
>
> Diffs
> -----
>
> proton-c/src/object/map.c 2e3b157
>
> Diff: https://reviews.apache.org/r/33750/diff/
>
>
> Testing
> -------
>
> The second unit test covers this case (as well as some others). My stress testing has also shown no issue with it.
>
>
> Thanks,
>
> Gordon Sim
>
>
Re: Review Request 33750: Optimisation of map entry deletion
Posted by Andrew Stitcher <as...@apache.org>.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/33750/#review82247
-----------------------------------------------------------
I see nothing wrong with the code.
However I do tend to agree with Rafi that this makes the code more complex and even less easy to understand then it already was.
A big help would be a block comment describing the implementation at the top of the file with text diagrams etc.
Perhaps more important would be a description somewhere of the data structure invariants.
- Andrew Stitcher
On May 1, 2015, 9:59 a.m., Gordon Sim wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/33750/
> -----------------------------------------------------------
>
> (Updated May 1, 2015, 9:59 a.m.)
>
>
> Review request for qpid, Alan Conway, Andrew Stitcher, and Rafael Schloming.
>
>
> Repository: qpid-proton-git
>
>
> Description
> -------
>
> This implements the optimisation suggested by Alan. If the next entry in a chain after the one being deleted is in the cellar (i.e. is non-addressable), then there is no need to rehahs, that next entry can simply be copied into the slot being deleted,and the next slot can be freed.
>
>
> Diffs
> -----
>
> proton-c/src/object/map.c 2e3b157
>
> Diff: https://reviews.apache.org/r/33750/diff/
>
>
> Testing
> -------
>
> The second unit test covers this case (as well as some others). My stress testing has also shown no issue with it.
>
>
> Thanks,
>
> Gordon Sim
>
>