Concurrent Rehashing. What is “rehashed segment” in multilevel rehashing?
Looking for an algorithm for implementing concurrent hash tables that don't rehash the entire table each time it needs to resize it I found the following paper:
Per-bucket concurrent rehashing algorithms
The "Multilevel rehashing" concept got my attention. The paper says:
2.3 Multilevel rehashing
The drawbacks of recursive hashing may be addressed by extending
buckets with a more complex control field that indicates the number of
segments rehashed. So, any operation accessing an "old" bucket can
detect whether rehashing is necessary and move the data directly into
all the new buckets available at once as shown in Figure 3.
Nevertheless, recursive rehashing may be a better choice when resizing
is a rare event and there is no space for additional field in the
bucket.
But I don't get it. What are rehashed segments?
The paper later says:
For multilevel rehashing, this check is trivial using information
about rehashed segments stored in the bucket, which in fact is current
capacity effective for the given bucket. The difficulty here is rather
in algorithm of detecting a correct root parent while other threads
can rehash it concurrently (not discussed in the paper).
Again, What are rehashed segments?
algorithm hashtable
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
add a comment |
Looking for an algorithm for implementing concurrent hash tables that don't rehash the entire table each time it needs to resize it I found the following paper:
Per-bucket concurrent rehashing algorithms
The "Multilevel rehashing" concept got my attention. The paper says:
2.3 Multilevel rehashing
The drawbacks of recursive hashing may be addressed by extending
buckets with a more complex control field that indicates the number of
segments rehashed. So, any operation accessing an "old" bucket can
detect whether rehashing is necessary and move the data directly into
all the new buckets available at once as shown in Figure 3.
Nevertheless, recursive rehashing may be a better choice when resizing
is a rare event and there is no space for additional field in the
bucket.
But I don't get it. What are rehashed segments?
The paper later says:
For multilevel rehashing, this check is trivial using information
about rehashed segments stored in the bucket, which in fact is current
capacity effective for the given bucket. The difficulty here is rather
in algorithm of detecting a correct root parent while other threads
can rehash it concurrently (not discussed in the paper).
Again, What are rehashed segments?
algorithm hashtable
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
I may be missing something, but how, exactly, does your question related to C++, or C#? I see nothing specific to those languages, in your question.
– Algirdas Preidžius
Nov 12 '18 at 13:05
@AlgirdasPreidžius It's related to c++ because the paper uses some pseudo c++ code. I would be happy with some c++ or c# code to explain things or give examples.
– Jesús López
Nov 12 '18 at 13:07
2
explain and elaborate is too broad for this site.
– Patrick Hofman
Nov 12 '18 at 13:09
1
@JesúsLópez 1) Pseudo code is pseudo code. It doesn't mean to represent a specific language. 2) Sure, paper does that. I was asking how does your question related to those languages? Especially, since C++ is quite different from C#.
– Algirdas Preidžius
Nov 12 '18 at 13:09
@PatrickHofman. Edited, just ask what a rehashed segment is?
– Jesús López
Nov 12 '18 at 13:47
add a comment |
Looking for an algorithm for implementing concurrent hash tables that don't rehash the entire table each time it needs to resize it I found the following paper:
Per-bucket concurrent rehashing algorithms
The "Multilevel rehashing" concept got my attention. The paper says:
2.3 Multilevel rehashing
The drawbacks of recursive hashing may be addressed by extending
buckets with a more complex control field that indicates the number of
segments rehashed. So, any operation accessing an "old" bucket can
detect whether rehashing is necessary and move the data directly into
all the new buckets available at once as shown in Figure 3.
Nevertheless, recursive rehashing may be a better choice when resizing
is a rare event and there is no space for additional field in the
bucket.
But I don't get it. What are rehashed segments?
The paper later says:
For multilevel rehashing, this check is trivial using information
about rehashed segments stored in the bucket, which in fact is current
capacity effective for the given bucket. The difficulty here is rather
in algorithm of detecting a correct root parent while other threads
can rehash it concurrently (not discussed in the paper).
Again, What are rehashed segments?
algorithm hashtable
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
Looking for an algorithm for implementing concurrent hash tables that don't rehash the entire table each time it needs to resize it I found the following paper:
Per-bucket concurrent rehashing algorithms
The "Multilevel rehashing" concept got my attention. The paper says:
2.3 Multilevel rehashing
The drawbacks of recursive hashing may be addressed by extending
buckets with a more complex control field that indicates the number of
segments rehashed. So, any operation accessing an "old" bucket can
detect whether rehashing is necessary and move the data directly into
all the new buckets available at once as shown in Figure 3.
Nevertheless, recursive rehashing may be a better choice when resizing
is a rare event and there is no space for additional field in the
bucket.
But I don't get it. What are rehashed segments?
The paper later says:
For multilevel rehashing, this check is trivial using information
about rehashed segments stored in the bucket, which in fact is current
capacity effective for the given bucket. The difficulty here is rather
in algorithm of detecting a correct root parent while other threads
can rehash it concurrently (not discussed in the paper).
Again, What are rehashed segments?
algorithm hashtable
algorithm hashtable
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
edited Nov 12 '18 at 14:31
Jesús López
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
asked Nov 12 '18 at 13:03
Jesús LópezJesús López
4,12211341
4,12211341
I may be missing something, but how, exactly, does your question related to C++, or C#? I see nothing specific to those languages, in your question.
– Algirdas Preidžius
Nov 12 '18 at 13:05
@AlgirdasPreidžius It's related to c++ because the paper uses some pseudo c++ code. I would be happy with some c++ or c# code to explain things or give examples.
– Jesús López
Nov 12 '18 at 13:07
2
explain and elaborate is too broad for this site.
– Patrick Hofman
Nov 12 '18 at 13:09
1
@JesúsLópez 1) Pseudo code is pseudo code. It doesn't mean to represent a specific language. 2) Sure, paper does that. I was asking how does your question related to those languages? Especially, since C++ is quite different from C#.
– Algirdas Preidžius
Nov 12 '18 at 13:09
@PatrickHofman. Edited, just ask what a rehashed segment is?
– Jesús López
Nov 12 '18 at 13:47
add a comment |
I may be missing something, but how, exactly, does your question related to C++, or C#? I see nothing specific to those languages, in your question.
– Algirdas Preidžius
Nov 12 '18 at 13:05
@AlgirdasPreidžius It's related to c++ because the paper uses some pseudo c++ code. I would be happy with some c++ or c# code to explain things or give examples.
– Jesús López
Nov 12 '18 at 13:07
2
explain and elaborate is too broad for this site.
– Patrick Hofman
Nov 12 '18 at 13:09
1
@JesúsLópez 1) Pseudo code is pseudo code. It doesn't mean to represent a specific language. 2) Sure, paper does that. I was asking how does your question related to those languages? Especially, since C++ is quite different from C#.
– Algirdas Preidžius
Nov 12 '18 at 13:09
@PatrickHofman. Edited, just ask what a rehashed segment is?
– Jesús López
Nov 12 '18 at 13:47
I may be missing something, but how, exactly, does your question related to C++, or C#? I see nothing specific to those languages, in your question.
– Algirdas Preidžius
Nov 12 '18 at 13:05
I may be missing something, but how, exactly, does your question related to C++, or C#? I see nothing specific to those languages, in your question.
– Algirdas Preidžius
Nov 12 '18 at 13:05
@AlgirdasPreidžius It's related to c++ because the paper uses some pseudo c++ code. I would be happy with some c++ or c# code to explain things or give examples.
– Jesús López
Nov 12 '18 at 13:07
@AlgirdasPreidžius It's related to c++ because the paper uses some pseudo c++ code. I would be happy with some c++ or c# code to explain things or give examples.
– Jesús López
Nov 12 '18 at 13:07
2
2
explain and elaborate is too broad for this site.
– Patrick Hofman
Nov 12 '18 at 13:09
explain and elaborate is too broad for this site.
– Patrick Hofman
Nov 12 '18 at 13:09
1
1
@JesúsLópez 1) Pseudo code is pseudo code. It doesn't mean to represent a specific language. 2) Sure, paper does that. I was asking how does your question related to those languages? Especially, since C++ is quite different from C#.
– Algirdas Preidžius
Nov 12 '18 at 13:09
@JesúsLópez 1) Pseudo code is pseudo code. It doesn't mean to represent a specific language. 2) Sure, paper does that. I was asking how does your question related to those languages? Especially, since C++ is quite different from C#.
– Algirdas Preidžius
Nov 12 '18 at 13:09
@PatrickHofman. Edited, just ask what a rehashed segment is?
– Jesús López
Nov 12 '18 at 13:47
@PatrickHofman. Edited, just ask what a rehashed segment is?
– Jesús López
Nov 12 '18 at 13:47
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53262790%2fconcurrent-rehashing-what-is-rehashed-segment-in-multilevel-rehashing%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53262790%2fconcurrent-rehashing-what-is-rehashed-segment-in-multilevel-rehashing%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I may be missing something, but how, exactly, does your question related to C++, or C#? I see nothing specific to those languages, in your question.
– Algirdas Preidžius
Nov 12 '18 at 13:05
@AlgirdasPreidžius It's related to c++ because the paper uses some pseudo c++ code. I would be happy with some c++ or c# code to explain things or give examples.
– Jesús López
Nov 12 '18 at 13:07
2
explain and elaborate is too broad for this site.
– Patrick Hofman
Nov 12 '18 at 13:09
1
@JesúsLópez 1) Pseudo code is pseudo code. It doesn't mean to represent a specific language. 2) Sure, paper does that. I was asking how does your question related to those languages? Especially, since C++ is quite different from C#.
– Algirdas Preidžius
Nov 12 '18 at 13:09
@PatrickHofman. Edited, just ask what a rehashed segment is?
– Jesús López
Nov 12 '18 at 13:47