> On April 28, 2015, 2:33 p.m., Alan Conway wrote: > > proton-c/src/object/map.c, line 322 > > <https://reviews.apache.org/r/33623/diff/2/?file=944061#file944061line322> > > > > Just to see if I understand the problem: > > > > The old code moves the "next" entry into the current slot. This breaks > > if the next entry is in allocated space and is the head of a coalesced > > chain as the latter part of that chain is now under the wrong bucket. > > > > So a simple optimization is to keep the original solution if (next > > > allocated) That is a very cheap way to check if there is a coalesced chain > > to worry about. > > Gordon Sim wrote: > Yes, I believe that is right, you can move the next entry as long as it > is outside the addressable region. I'll make (and test) that change. > > Andrew Stitcher wrote: > I don't think that test is correct: nodes in the hash chain can be in > both the "addressable" and "non-addressable" region, it's just that you don't > use the addressable region unless there is no more space in the > "non-addressable" region. The scan for a free table entry starts at the last > entry but can reach all the way to the first table entry not just the first > entry in the non-addressable region. > > Gordon Sim wrote: > I don't understand your point. > > Andrew Stitcher wrote: > I'm trying to say that Alan's suggested optimisation is incorrect.
Can you elaborate as to why not? Above you state the nodes can be in the addressable region as well as outside it, which is obvious, but you don't say why it is incorrect to move an entry out of the non-addressable region. I believe it is moving addressable entries that is the problem (as this is what breaks the link to the hashing). - Gordon ----------------------------------------------------------- This is an automatically generated e-mail. To reply, visit: https://reviews.apache.org/r/33623/#review81814 ----------------------------------------------------------- On April 28, 2015, 12:50 p.m., Gordon Sim wrote: > > ----------------------------------------------------------- > This is an automatically generated e-mail. To reply, visit: > https://reviews.apache.org/r/33623/ > ----------------------------------------------------------- > > (Updated April 28, 2015, 12:50 p.m.) > > > Review request for qpid, Alan Conway, Andrew Stitcher, and Rafael Schloming. > > > Bugs: PROTON-858 > https://issues.apache.org/jira/browse/PROTON-858 > > > Repository: qpid-proton-git > > > Description > ------- > > The internal map implementation for proton-c uses coalesced hashing, but the > current deletion algorithm does not take account of this. On deletion of > entries, the map can lose its ability to locate other entries by key. > > This patch is the simplest possible fix. It frees the deleted entry, makes > any previous entry that points to this tha tail of its chain, and then > relocates any entries in a chain following the deleted entry. Though I > believe this to be correct and safe, it does involve more work on some > deletions. The approach can be optimised further, either be reducing the > amount of chain that needs relocated, or by marking records as deleted in the > first instance and only rehashing later on some criteria. > > (I started off trying to do the latter, but it is more complicated and I > still haven't got my patch fully correct. When I get that working I'll post > that also. It is a more involved change though, so perhaps we may want to > consider this simpler approach for 0.9.1). > > > Diffs > ----- > > proton-c/src/object/map.c 1a758a1 > > Diff: https://reviews.apache.org/r/33623/diff/ > > > Testing > ------- > > > Thanks, > > Gordon Sim > >
