You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "zanmato1984 (via GitHub)" <gi...@apache.org> on 2024/12/24 02:31:07 UTC
[PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
zanmato1984 opened a new pull request, #45104:
URL: https://github.com/apache/arrow/pull/45104
<!--
Thanks for opening a pull request!
If this is your first pull request you can find detailed information on how
to contribute here:
* [New Contributor's Guide](https://arrow.apache.org/docs/dev/developers/guide/step_by_step/pr_lifecycle.html#reviews-and-merge-of-the-pull-request)
* [Contributing Overview](https://arrow.apache.org/docs/dev/developers/overview.html)
If this is not a [minor PR](https://github.com/apache/arrow/blob/main/CONTRIBUTING.md#Minor-Fixes). Could you open an issue for this pull request on GitHub? https://github.com/apache/arrow/issues/new/choose
Opening GitHub issues ahead of time contributes to the [Openness](http://theapacheway.com/open/#:~:text=Openness%20allows%20new%20users%20the,must%20happen%20in%20the%20open.) of the Apache Arrow project.
Then could you also rename the pull request title in the following format?
GH-${GITHUB_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
or
MINOR: [${COMPONENT}] ${SUMMARY}
-->
### Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
### What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
### Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
### Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please uncomment the line below and explain which changes are breaking.
-->
<!-- **This PR includes breaking changes to public APIs.** -->
<!--
Please uncomment the line below (and provide explanation) if the changes fix either (a) a security vulnerability, (b) a bug that caused incorrect or invalid data to be produced, or (c) a bug that causes a crash (even when the API contract is upheld). We use this to highlight fixes to issues that may affect users without their knowledge. For this reason, fixing bugs that cause errors don't count, since those are usually obvious.
-->
<!-- **This PR contains a "Critical Fix".** -->
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "kou (via GitHub)" <gi...@apache.org>.
kou commented on code in PR #45104:
URL: https://github.com/apache/arrow/pull/45104#discussion_r1896409866
##########
cpp/src/arrow/compute/key_map_internal.cc:
##########
@@ -281,7 +281,7 @@ void SwissTable::early_filter_imp(const int num_keys, const uint32_t* hashes,
// When we reach this limit, we need to break processing of any further rows and resize.
//
uint64_t SwissTable::num_groups_for_resize() const {
- // Resize small hash tables when 50% full (up to 12KB).
+ // Resize small hash tables when 50% full (up to 32KB).
Review Comment:
Sorry, how to compute `32KB`?
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #45104:
URL: https://github.com/apache/arrow/pull/45104#discussion_r1896416872
##########
cpp/src/arrow/compute/key_map_internal.cc:
##########
@@ -281,7 +281,7 @@ void SwissTable::early_filter_imp(const int num_keys, const uint32_t* hashes,
// When we reach this limit, we need to break processing of any further rows and resize.
//
uint64_t SwissTable::num_groups_for_resize() const {
- // Resize small hash tables when 50% full (up to 12KB).
+ // Resize small hash tables when 50% full (up to 32KB).
Review Comment:
The `log_blocks_small = 9` means that we consider `1 << 9 = 512` blocks as "small". A block is a swiss-table-specific concept explained in https://github.com/apache/arrow/blob/main/cpp/src/arrow/acero/doc/key_map.md , which is 64-byte. So the small hash table ends up with `512 * 64B = 32KB`.
So the original `12KB` is obviously a typo.
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "kou (via GitHub)" <gi...@apache.org>.
kou commented on code in PR #45104:
URL: https://github.com/apache/arrow/pull/45104#discussion_r1896435485
##########
cpp/src/arrow/compute/key_map_internal.cc:
##########
@@ -281,7 +281,7 @@ void SwissTable::early_filter_imp(const int num_keys, const uint32_t* hashes,
// When we reach this limit, we need to break processing of any further rows and resize.
//
uint64_t SwissTable::num_groups_for_resize() const {
- // Resize small hash tables when 50% full (up to 12KB).
+ // Resize small hash tables when 50% full (up to 32KB).
Review Comment:
Thanks!
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #45104:
URL: https://github.com/apache/arrow/pull/45104#issuecomment-2560647624
cc @kou @pitrou
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 merged PR #45104:
URL: https://github.com/apache/arrow/pull/45104
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #45104:
URL: https://github.com/apache/arrow/pull/45104#discussion_r1896302132
##########
cpp/src/arrow/acero/doc/key_map.md:
##########
@@ -65,7 +65,7 @@ Every slot can either be **empty** or store data related to a single inserted ke
Status byte, as the name suggests, stores 8 bits. The highest bit indicates if the slot is empty (the highest bit is set) or corresponds to one of inserted keys (the highest bit is zero). The remaining 7 bits contain 7 bits of key hash that we call a **stamp**. The stamp is used to eliminate some false positives when searching for a matching key for a given input. Slot also stores **key id**, which is a non-negative integer smaller than the number of inserted keys, that is used as a reference to the actual inserted key. The last piece of information related to an inserted key is its **hash** value. We store hashes for all keys, so that they never need to be re-computed. That greatly simplifies some operations, like resizing of a hash table, that may not even need to look at the keys at all. For an empty slot, the status byte is 0x80, key id is zero and the hash is not used and can be set to any number.
-A single block contains 8 slots and can be viewed as a micro-stack of up to 8 inserted keys. When the first key is inserted into an empty block, it will occupy a slot with local id 0. The second inserted key will go into slot number 1 and so on. We use N highest bits of hash to get an index of a **start block**, when searching for a match or an empty slot to insert a previously not seen key when that is the case. If the start block contains any empty slots, then the search for either a match or place to insert a key will end at that block. We will call such a block an **open block**. A block that is not open is a full block. In the case of full block, the input key related search may continue in the next block module the number of blocks. If the key is not inserted into its start block, we will refer to it as an **overflow** entry, other entries being **non-overflow**. Overflow entries are slower to process, since they require visiting more than one block, so we want to keep their p
ercentage low. This is done by choosing the right **load factor** (percentage of occupied slots in the hash table) at which the hash table gets resized and the number of blocks gets doubled. By tuning this value we can control the probability of encountering an overflow entry.
+A single block contains 8 slots and can be viewed as a micro-stack of up to 8 inserted keys. When the first key is inserted into an empty block, it will occupy a slot with local id 0. The second inserted key will go into slot number 1 and so on. We use N highest bits of hash to get an index of a **start block**, when searching for a match or an empty slot to insert a previously not seen key when that is the case. If the start block contains any empty slots, then the search for either a match or place to insert a key will end at that block. We will call such a block an **open block**. A block that is not open is a full block. In the case of full block, the input key related search may continue in the next block modulo the number of blocks. If the key is not inserted into its start block, we will refer to it as an **overflow** entry, other entries being **non-overflow**. Overflow entries are slower to process, since they require visiting more than one block, so we want to keep their p
ercentage low. This is done by choosing the right **load factor** (percentage of occupied slots in the hash table) at which the hash table gets resized and the number of blocks gets doubled. By tuning this value we can control the probability of encountering an overflow entry.
Review Comment:
module -> modulo
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #45104:
URL: https://github.com/apache/arrow/pull/45104#issuecomment-2560713696
The CI failure is unrelated. I'm merging this.
Thank you @kou for looking!
--
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
Re: [PR] MINOR: [C++] Fix typos in key_map doc and comment [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #45104:
URL: https://github.com/apache/arrow/pull/45104#issuecomment-2585555115
After merging your PR, Conbench analyzed the 4 benchmarking runs that have been run so far on merge-commit e7471f85b45a0f547bf5395bd98f8d6d8aa0af78.
There were no benchmark performance regressions. 🎉
The [full Conbench report](https://github.com/apache/arrow/runs/35482091704) has more details. It also includes information about 42 possible false positives for unstable benchmarks that are known to sometimes produce them.
--
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