You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@camel.apache.org by "gnodet (via GitHub)" <gi...@apache.org> on 2026/06/04 12:02:43 UTC

[PR] Improve CaseInsensitiveMap: O(1) hash table with zero-alloc lookups and header key deduplication [camel]

gnodet opened a new pull request, #23766:
URL: https://github.com/apache/camel/pull/23766

   ## Summary
   
   Replace the `TreeMap`-based `CaseInsensitiveMap` with a custom hash table implementation, improving the performance of every header access in every Camel route.
   
   `CaseInsensitiveMap` is the default headers map for every `Exchange` in Camel. It is the most accessed data structure in the framework — every `message.getHeader()`, `setHeader()`, `removeHeader()`, and header iteration goes through it.
   
   ### Before (TreeMap with `CASE_INSENSITIVE_ORDER`)
   - **O(log n)** for `get`, `put`, `containsKey`, `remove`
   - String comparisons at every tree node during lookup
   - Deserialized header keys allocate duplicate `String` objects across exchanges
   - To get O(1), users needed the `camel-headersmap` dependency (cedarsoftware `java-util`, which uses `ThreadLocal` internally — problematic with virtual threads)
   
   ### After (custom hash table)
   - **O(1)** for `get`, `put`, `containsKey`, `remove`
   - **Zero allocation on lookups** — case-insensitive hash computed char-by-char with `Character.toLowerCase(Character.toUpperCase(c))`, keys compared with `equalsIgnoreCase()`. No `toLowerCase()` string copies
   - **Header key deduplication** — well-known `Exchange` header constants (141 keys) are registered at startup; deserialized keys matching a known constant are replaced with the canonical interned reference, reducing memory across exchanges
   - Entries stored in **insertion order** (deterministic iteration)
   - Original key case preserved (first-put case wins, same as before)
   - No external dependencies, no `ThreadLocal`
   - Eliminates the need for `camel-headersmap` in most cases
   
   ### Design
   
   The map extends `AbstractMap` and implements its own hash table with separate chaining using parallel arrays (`keys[]`, `values[]`, `chainNext[]`). This gives cache-friendly storage and avoids per-entry object allocation overhead of `HashMap.Node`.
   
   The hash function uses the same two-step fold as `String.equalsIgnoreCase()` — `Character.toLowerCase(Character.toUpperCase(c))` — ensuring hash consistency even for Unicode edge cases (e.g., Turkish dotless-ı).
   
   `DefaultHeadersMapFactory` registers all `Exchange` string constants at startup via `CaseInsensitiveMap.registerKnownKeys()`. On `put()`, a zero-allocation lookup in the static known-keys table replaces deserialized keys with canonical references.
   
   ### Compatibility
   
   - The `Map<String, Object>` API is unchanged
   - `DefaultHeadersMapFactory` and `instanceof CaseInsensitiveMap` checks work as before
   - No code in the codebase uses `SortedMap`/`NavigableMap` methods on this map
   - Iteration order changes from alphabetical (TreeMap) to insertion order — no code depends on alphabetical ordering
   - All existing tests pass; 10 new tests added
   
   ## Test plan
   
   - [x] `CaseInsensitiveMapTest` — 32 tests (+ 10 new: insertion order, iterator removal, entry setValue, entrySet remove, remove-then-reput, resize/rehash, containsValue, null values, clear-reuse, known key deduplication)
   - [x] `DefaultMessageHeaderTest` — 16 tests
   - [x] Formatter and import sort clean


-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Improve CaseInsensitiveMap: O(1) hash table with zero-alloc lookups and header key deduplication [camel]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #23766:
URL: https://github.com/apache/camel/pull/23766#issuecomment-4622190490

   <!-- ci-tested-modules -->
   :test_tube: **CI tested the following changed modules:**
   
   - `core/camel-base-engine`
   - `core/camel-core`
   - `core/camel-util`
   
   > :information_source: Dependent modules were not tested because the total number of affected modules exceeded the threshold (50). Use the `test-dependents` label to force testing all dependents.
   
   :warning: **Some tests are disabled on GitHub Actions** (`@DisabledIfSystemProperty(named = "ci.env.name")`) and require manual verification:
   
   - `core/camel-core`: 2 test(s) disabled on GitHub Actions
   
   <details><summary>Build reactor — dependencies compiled but only changed modules were tested (3 modules)</summary>
   
   - Camel :: Base Engine
   - Camel :: Core
   - Camel :: Util
   
   </details>
   
   ---
   :gear: [View full build and test results](https://github.com/apache/camel/actions/runs/26950487631)


-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Improve CaseInsensitiveMap: O(1) hash table with zero-alloc lookups and header key deduplication [camel]

Posted by "davsclaus (via GitHub)" <gi...@apache.org>.
davsclaus commented on code in PR #23766:
URL: https://github.com/apache/camel/pull/23766#discussion_r3356236032


##########
core/camel-base-engine/src/main/java/org/apache/camel/impl/engine/DefaultHeadersMapFactory.java:
##########
@@ -29,6 +33,22 @@
  */
 public class DefaultHeadersMapFactory implements HeadersMapFactory {
 
+    static {
+        List<String> keys = new ArrayList<>();
+        for (Field f : Exchange.class.getFields()) {

Review Comment:
   There is a ExchangeConstantProvider that carry all those known keys. Can this be used to avoid reflection, which maybe is also a problem for Quarkus



-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Improve CaseInsensitiveMap: O(1) hash table with zero-alloc lookups and header key deduplication [camel]

Posted by "davsclaus (via GitHub)" <gi...@apache.org>.
davsclaus commented on PR #23766:
URL: https://github.com/apache/camel/pull/23766#issuecomment-4625110220

   https://issues.apache.org/jira/browse/CAMEL-23689


-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Improve CaseInsensitiveMap: O(1) hash table with zero-alloc lookups and header key deduplication [camel]

Posted by "gnodet (via GitHub)" <gi...@apache.org>.
gnodet commented on PR #23766:
URL: https://github.com/apache/camel/pull/23766#issuecomment-4623029160

   _Claude Code on behalf of Guillaume Nodet_
   
   Addressed review feedback: replaced reflection with `ExchangeConstantProvider.values()`. Added a `values()` method to the generated constant provider class (via the Velocity template in `camel-package-maven-plugin`) so `DefaultHeadersMapFactory` can register known keys without reflection — Quarkus-friendly.


-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] CAMEL-23691: Improve CaseInsensitiveMap with O(1) hash table and header key deduplication [camel]

Posted by "gnodet (via GitHub)" <gi...@apache.org>.
gnodet merged PR #23766:
URL: https://github.com/apache/camel/pull/23766


-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Improve CaseInsensitiveMap: O(1) hash table with zero-alloc lookups and header key deduplication [camel]

Posted by "davsclaus (via GitHub)" <gi...@apache.org>.
davsclaus commented on PR #23766:
URL: https://github.com/apache/camel/pull/23766#issuecomment-4623492330

   We can deprecate camel-headersmap 


-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Improve CaseInsensitiveMap: O(1) hash table with zero-alloc lookups and header key deduplication [camel]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #23766:
URL: https://github.com/apache/camel/pull/23766#issuecomment-4621978532

   :star2: Thank you for your contribution to the Apache Camel project! :star2:
     :robot: CI automation will test this PR automatically.
   
     :camel: Apache Camel Committers, please review the following items:
   
     * First-time contributors **require MANUAL approval** for the GitHub Actions to run
     * You can use the command `/component-test (camel-)component-name1 (camel-)component-name2..` to request a test from the test bot although they are normally detected and executed by CI.
     * You can label PRs using `skip-tests` and `test-dependents` to fine-tune the checks executed by this PR.
     * Build and test logs are available in the summary page. **Only** [Apache Camel committers](https://camel.apache.org/community/team/#committers) have access to the summary.
     
     :warning: Be careful when sharing logs. Review their contents before sharing them publicly.


-- 
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: commits-unsubscribe@camel.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org