MCPcopy Create free account
hub / github.com/apache/arrow / TEST

Function TEST

cpp/src/arrow/compute/key_map_test.cc:38–81  ·  view source on GitHub ↗

With 32-bit group ids a block takes 40 bytes, so the byte offsets of the blocks from id ceil(2^32 / 40) on do not fit in 32 bits.

Source from the content-addressed store, hash-verified

36// With 32-bit group ids a block takes 40 bytes, so the byte offsets of the blocks from
37// id ceil(2^32 / 40) on do not fit in 32 bits.
38TEST(SwissTable, LARGE_MEMORY_TEST(EarlyFilterOver4GB)) {
39 if constexpr (sizeof(void*) == 4) {
40 GTEST_SKIP() << "Test only works on 64-bit platforms";
41 }
42
43 // 2^27 blocks of 40 bytes take 5GB.
44 constexpr int kLogBlocks = 27;
45 constexpr uint32_t kFirstBlockOver4GB = 107374183;
46 constexpr int kNumHashes = 16;
47
48 // One hash for each of the 8 blocks below and the 8 blocks above the 4GB boundary,
49 // all with a non-zero stamp.
50 std::vector<uint32_t> hashes(kNumHashes);
51 for (int i = 0; i < kNumHashes; ++i) {
52 uint32_t block_id = kFirstBlockOver4GB - kNumHashes / 2 + i;
53 hashes[i] = (block_id << (SwissTable::bits_hash_ - kLogBlocks)) | 1;
54 }
55
56 for (int64_t hardware_flags : GetSupportedHardwareFlags({CpuInfo::AVX2})) {
57 ARROW_SCOPED_TRACE("hardware_flags = ", hardware_flags);
58 SwissTable table;
59 ASSERT_OK(table.init(hardware_flags, default_memory_pool(), kLogBlocks,
60 /*no_hash_array=*/true));
61 // Insert every other hash into the first slot of its block, leaving the other blocks
62 // empty.
63 for (int i = 0; i < kNumHashes; i += 2) {
64 uint32_t block_id = SwissTable::block_id_from_hash(hashes[i], kLogBlocks);
65 table.insert_into_empty_slot(SwissTable::global_slot_id(block_id, 0), hashes[i],
66 /*group_id=*/i);
67 }
68
69 uint8_t match_bitvector[kNumHashes / 8];
70 uint8_t local_slots[kNumHashes];
71 table.early_filter(kNumHashes, hashes.data(), match_bitvector, local_slots);
72 for (int i = 0; i < kNumHashes; ++i) {
73 ARROW_SCOPED_TRACE("block_id = ",
74 SwissTable::block_id_from_hash(hashes[i], kLogBlocks));
75 // Inserted hashes match in the first slot, the others hit an empty block whose
76 // first slot is empty.
77 ASSERT_EQ(bit_util::GetBit(match_bitvector, i), i % 2 == 0);
78 ASSERT_EQ(local_slots[i], 0);
79 }
80 }
81}
82
83// When growing to a table over 4GB, entries that have to move past a full block must
84// still land in the right block.

Callers

nothing calls this directly

Calls 13

default_memory_poolFunction · 0.85
block_id_from_hashFunction · 0.85
global_slot_idFunction · 0.85
early_filterMethod · 0.80
map_new_keysMethod · 0.80
GetBitFunction · 0.50
OKFunction · 0.50
initMethod · 0.45
dataMethod · 0.45
InitMethod · 0.45

Tested by

no test coverage detected