Reduce redundant calculations between prefetching and dictionary lookup. PiperOrigin-RevId: 990412667
diff --git a/c/enc/backward_references.c b/c/enc/backward_references.c index c78d902..1a7d3d0 100644 --- a/c/enc/backward_references.c +++ b/c/enc/backward_references.c
@@ -214,7 +214,7 @@ #define HASHER() H59 /* NOLINTNEXTLINE(build/include) */ -#include "backward_references_inc_opt.h" +#include "backward_references_opt_inc.h" #undef HASHER #define HASHER() H68 @@ -271,7 +271,7 @@ #undef HASHER #define HASHER() H59 /* NOLINTNEXTLINE(build/include) */ -#include "backward_references_inc_opt.h" +#include "backward_references_opt_inc.h" #undef HASHER #define HASHER() H68 /* NOLINTNEXTLINE(build/include) */
diff --git a/c/enc/backward_references_inc_opt.h b/c/enc/backward_references_opt_inc.h similarity index 93% rename from c/enc/backward_references_inc_opt.h rename to c/enc/backward_references_opt_inc.h index d26c282..b9a14eb 100644 --- a/c/enc/backward_references_inc_opt.h +++ b/c/enc/backward_references_opt_inc.h
@@ -29,6 +29,9 @@ LiteralSpreeLengthForSparseSearch(params); size_t apply_random_heuristics = position + random_heuristics_window_size; const size_t gap = params->dictionary.compound.total_size; + /* Compound-dictionary probe state: written by the prefetch helper before + each FindLongestMatch, consumed by the lookup after it. */ + PreparedDictionaryProbe dict_probes[SHARED_BROTLI_MAX_COMPOUND_DICTS + 1]; /* Minimum score to accept a backward reference. */ const score_t kMinScore = BROTLI_SCORE_BASE + 100; @@ -111,15 +114,16 @@ sr.score = kMinScore; if (ENABLE_COMPOUND_DICTIONARY) { PrefetchCompoundDictionaryMatchOpt(¶ms->dictionary.compound, - ringbuffer, ringbuffer_mask, position); + ringbuffer, ringbuffer_mask, position, dict_probes); } FN(FindLongestMatch)(privat, params->dictionary.contextual.dict[dict_id], ringbuffer, ringbuffer_mask, dist_cache, position, max_length, max_distance, dictionary_start + gap, params->dist.max_distance, &sr); if (ENABLE_COMPOUND_DICTIONARY) { - LookupCompoundDictionaryMatchOpt(¶ms->dictionary.compound, ringbuffer, - ringbuffer_mask, dist_cache, position, max_length, - dictionary_start, params->dist.max_distance, &sr); + LookupCompoundDictionaryMatchOpt( + ¶ms->dictionary.compound, dict_probes, ringbuffer, + ringbuffer_mask, dist_cache, position, max_length, dictionary_start, + params->dist.max_distance, &sr); } if (sr.score > kMinScore) { /* Found a match. Let's look for something even better ahead. */ @@ -144,7 +148,7 @@ } if (ENABLE_COMPOUND_DICTIONARY) { PrefetchCompoundDictionaryMatchOpt(¶ms->dictionary.compound, - ringbuffer, ringbuffer_mask, position + 1); + ringbuffer, ringbuffer_mask, position + 1, dict_probes); } FN(FindLongestMatch)(privat, params->dictionary.contextual.dict[dict_id], @@ -153,7 +157,7 @@ &sr2); if (ENABLE_COMPOUND_DICTIONARY) { LookupCompoundDictionaryMatchOpt( - ¶ms->dictionary.compound, ringbuffer, + ¶ms->dictionary.compound, dict_probes, ringbuffer, ringbuffer_mask, dist_cache, position + 1, max_length, dictionary_start, params->dist.max_distance, &sr2); }
diff --git a/c/enc/hash.h b/c/enc/hash.h index 8df275a..dc16d47 100644 --- a/c/enc/hash.h +++ b/c/enc/hash.h
@@ -747,9 +747,17 @@ return total_found; } +/* Struct for handing state between the prefetch and find calls. Avoids + * recalculating the hash and dependent variables. */ +typedef struct PreparedDictionaryProbe { + const uint32_t* chain; + uint32_t item; +} PreparedDictionaryProbe; + static BROTLI_INLINE void PrefetchCompoundDictionaryMatchOpt( const CompoundDictionary* addon, const uint8_t* BROTLI_RESTRICT data, - const size_t ring_buffer_mask, const size_t cur_ix) { + const size_t ring_buffer_mask, const size_t cur_ix, + PreparedDictionaryProbe* BROTLI_RESTRICT probes) { const size_t cur_ix_masked = cur_ix & ring_buffer_mask; const uint64_t bytes = BROTLI_UNALIGNED_LOAD64LE(&data[cur_ix_masked]); size_t d; @@ -762,38 +770,48 @@ const uint32_t head = view->heads[key]; /* Deliberately branchless - if head == 0xFFFF (no items), we'll prefetch * some garbage address. Prefetch can't fault, so this is safe.*/ - PREFETCH_L1(&view->items[view->slot_offsets[slot] + head]); + const uint32_t* chain = &view->items[view->slot_offsets[slot] + head]; + PREFETCH_L1(chain); + probes[d].chain = chain; + probes[d].item = (head == 0xFFFF) ? 1 : 0; } } static BROTLI_INLINE void FindCompoundDictionaryMatchOpt( - const PreparedDictionaryView* self, const uint8_t* BROTLI_RESTRICT data, + const PreparedDictionaryView* self, + const PreparedDictionaryProbe* BROTLI_RESTRICT probe, + const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask, const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix, const size_t max_length, const size_t distance_offset, const size_t max_distance, HasherSearchResult* BROTLI_RESTRICT out) { const uint32_t source_size = self->source_size; const size_t boundary = distance_offset - source_size; - const uint32_t hash_shift = self->hash_shift; - const uint32_t slot_mask = self->slot_mask; - const uint64_t hash_mask = self->hash_mask; - const uint32_t* slot_offsets = self->slot_offsets; - const uint16_t* heads = self->heads; - const uint32_t* items = self->items; const uint8_t* source = self->source; const size_t cur_ix_masked = cur_ix & ring_buffer_mask; score_t best_score = out->score; size_t best_len = out->len; size_t i; - const uint64_t h = - (BROTLI_UNALIGNED_LOAD64LE(&data[cur_ix_masked]) & hash_mask) * - kPreparedDictionaryHashMul64Long; - const uint32_t key = (uint32_t)(h >> hash_shift); - const uint32_t slot = key & slot_mask; - const uint32_t head = heads[key]; - const uint32_t* BROTLI_RESTRICT chain = &items[slot_offsets[slot] + head]; - uint32_t item = (head == 0xFFFF) ? 1 : 0; + /* The hash and hashtable offsets were calculated in Prefetch, reuse the + * results. */ + const uint32_t* BROTLI_RESTRICT chain = probe->chain; + uint32_t item = probe->item; +#if defined(BROTLI_DEBUG) || defined(BROTLI_ENABLE_LOG) + { + const uint64_t bytes = BROTLI_UNALIGNED_LOAD64LE(&data[cur_ix_masked]); + const uint64_t h = + (bytes & self->hash_mask) * kPreparedDictionaryHashMul64Long; + const uint32_t key = (uint32_t)(h >> self->hash_shift); + const uint32_t slot = key & self->slot_mask; + const uint32_t head = self->heads[key]; + const uint32_t* expected_chain = + &self->items[self->slot_offsets[slot] + head]; + const uint32_t expected_item = (head == 0xFFFF) ? 1 : 0; + BROTLI_DCHECK(probe->chain == expected_chain); + BROTLI_DCHECK(probe->item == expected_item); + } +#endif BROTLI_DCHECK(cur_ix_masked + max_length <= ring_buffer_mask + 1); @@ -866,7 +884,9 @@ } static BROTLI_INLINE void LookupCompoundDictionaryMatchOpt( - const CompoundDictionary* addon, const uint8_t* BROTLI_RESTRICT data, + const CompoundDictionary* addon, + const PreparedDictionaryProbe* BROTLI_RESTRICT probes, + const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask, const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix, const size_t max_length, const size_t max_ring_buffer_distance, const size_t max_distance, @@ -875,7 +895,7 @@ size_t d; for (d = 0; d < addon->num_chunks; ++d) { FindCompoundDictionaryMatchOpt( - &addon->chunk_views[d], data, ring_buffer_mask, + &addon->chunk_views[d], &probes[d], data, ring_buffer_mask, distance_cache, cur_ix, max_length, base_offset - addon->chunk_offsets[d], max_distance, sr); }
diff --git a/setup.py b/setup.py index b326304..88c1b38 100644 --- a/setup.py +++ b/setup.py
@@ -254,7 +254,7 @@ "c/enc/backward_references.h", "c/enc/backward_references_hq.h", "c/enc/backward_references_inc.h", - "c/enc/backward_references_inc_opt.h", + "c/enc/backward_references_opt_inc.h", "c/enc/bit_cost.h", "c/enc/bit_cost_inc.h", "c/enc/block_encoder_inc.h",