You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@arrow.apache.org by "Light-City (via GitHub)" <gi...@apache.org> on 2023/07/27 11:54:50 UTC
[GitHub] [arrow] Light-City opened a new issue, #36910: [C++] search_block may be wrong in SwissTable?
Light-City opened a new issue, #36910:
URL: https://github.com/apache/arrow/issues/36910
### Describe the bug, including details regarding any error messages, version, and platform.
## Describe the enhancement requested
key_map.cc search_block function.
document or code may be wrong?
If I follow the parameters in the documentation, I get inconsistent results.
The reference is as follows：
```
Example will use input stamp 0x5E and a 64-bit status bytes word with one empty slot:
0x 4B17 5E3A 5E2B 1180.
[1 instruction] Replicate stamp to all bytes by multiplying it by 0x 0101 0101 0101 0101.
We obtain: 0x 5E5E 5E5E 5E5E 5E5E.
[1 instruction] XOR replicated stamp with status bytes word. Bytes corresponding to a matching stamp will be 0, bytes corresponding to empty slots will have a value between 128 and 255, bytes corresponding to non-matching non-empty slots will have a value between 1 and 127.
We obtain: 0x 1549 0064 0075 4FDE.
[2 instructions] In the next step we want to have information about a match in the highest bit of each byte. We can ignore here empty slot bytes, because they will be taken care of at a later step. Set the highest bit in each byte (OR with 0x 8080 8080 8080 8080) and then subtract 1 from each byte (subtract 0x 0101 0101 0101 0101 from 64-bit word). Now if a byte corresponds to a non-empty slot then the highest bit 0 indicates a match and 1 indicates a miss.
We obtain: 0x 95C9 80E4 80F5 CFDE, then 0x 94C8 7FE3 7FF4 CEDD.
[3 instructions] In the next step we want to obtain in each byte one of two values: 0x80 if it is either an empty slot or a match, 0x00 otherwise. We do it in three steps: NOT the result of the previous step to change the meaning of the highest bit; OR with the original status word to set highest bit in a byte to 1 for empty slots; mask out everything other than the highest bits in all bytes (AND with 0x 8080 8080 8080 8080).
We obtain: 6B37 801C 800B 3122,
then 6B37 DE3E DE2B 31A2,
finally 0x0000 8000 8000 0080.
[2 instructions] Finally, use leading zero bits count and divide it by 8 to find an index of the last byte that corresponds either to a match or an empty slot. If the leading zero count intrinsic returns 64 for a 64-bit input zero, then after dividing by 8 we will also get the desired answer in case of a full block without any matches.
We obtain: 16,
then 2 (index of the first slot within the block that matches the stamp).
```
input stamp 0x5E
block is 0x 4B17 5E3A 5E2B 1180
but i got some diffenet result.
step 1:
```
// document result
0x 5E5E 5E5E 5E5E 5E5E
// acutal result
0x5e5e5e5e5e5e5e00
```
step 2:
```
// document result
0x 1549 0064 0075 4FDE
// acutal result
0x1549006400754f80
```
The results of the following steps are not the same, so I won’t go into details here.
Because, I guess there is a problem with the implementation of search_block?Especially step1 calculation.
```
// may be wrong???
uint64_t stamp_pattern = stamp * ((block_high_bits ^ kHighBitOfEachByte) >> 7);
```
## Component(s)
C++
### Component(s)
C++
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 closed issue #36910: [C++] search_block may be wrong in SwissTable?
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 closed issue #36910: [C++] search_block may be wrong in SwissTable?
URL: https://github.com/apache/arrow/issues/36910
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on issue #36910: [C++] search_block may be wrong in SwissTable?
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on issue #36910:
URL: https://github.com/apache/arrow/issues/36910#issuecomment-1653915479
I had a look at the code and the doc. You are right that they are not consistent with each other. However, I believe they are equivalent, and they only differ in the order of instructions: The code `AND with 0x 8080 8080 8080 8080` in the first step, but the doc does so in the last step. If you follow along the code till the end, you will get the same result `0x0000 8000 8000 0080` in the code.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] Light-City commented on issue #36910: [C++] search_block may be wrong in SwissTable?
Posted by "Light-City (via GitHub)" <gi...@apache.org>.
Light-City commented on issue #36910:
URL: https://github.com/apache/arrow/issues/36910#issuecomment-1654822312
> I had a look at the code and the doc. You are right that they are not consistent with each other. However, I believe they are equivalent, and they only differ in the order of instructions: The code `AND with 0x 8080 8080 8080 8080` in the first step, but the doc does so in the last step. If you follow along the code till the end, you will get the same result `0x0000 8000 8000 0080` as in the doc.
Indeed, I also ended up with consistent results
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org