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.
| 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. |
| 38 | TEST(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. |
nothing calls this directly
no test coverage detected