Hello,
On Wed, Oct 21, 2026 at 12:29:20PM +0900, Youngkwang Lee wrote:
> query_param_cmp() called iststop(param, '=') on both of its operands on
> every single comparison to find where the parameter name ends. qsort()
> performs O(n log n) comparisons, so each parameter name was rescanned
> about log2(n) times: for a query string with 427 parameters that is
> roughly 7400 scans to recover 427 pieces of information.
>
> The collection loop already walks every parameter once, so locate '='
> there and remember the name length alongside the parameter. This turns
> the O(n log n) rescanning into a single O(n) pass.
>
> Storing the extra length requires a dedicated struct rather than a bare
> struct ist. It is laid out as a pointer plus two 32 bit lengths, which
> keeps it at 16 bytes on 64-bit platforms, exactly the size of the
> struct ist it replaces, so the number of parameters that fit into the
> trash chunk is unchanged and the existing ERR_ALLOC threshold is
> preserved there. On 32-bit platforms it is 12 bytes instead of 8, which
> reduces that number by a third; queries with more parameters than fit
> are rejected with ERR_ALLOC as before, just from a lower bound. Both
> lengths are bounded by the buffer size, so 32 bits are always
> sufficient.
>
> The resulting order is identical: the same names are compared with the
> same istdiff(), and the pointer comparison that makes the sort stable
> for identical names is kept.
>
> Measured on a 24-core AMD EPYC 7413 with a 20 kB query string
> (427 parameters), gcc -O2, requests handled with keep-alive, comparing
> the six normalizers before and after this series:
>
> 8 byte path 266.4 us -> 266.0 us (no measurable change)
> 60 parameter query 314.02 us -> 311.17 us -0.9%
> 427 parameter query 1137.52 us -> 1062.53 us -6.6%
>
> Those are whole-request figures, where normalization is only a part of
> the cost. Against a build with the six actions removed the same 427
> parameter case costs 989.67 us, so what the actions themselves add goes
> from 218.3 us down to 142.9 us, about a third less:
>
> normalization overhead +218.3 us -> +142.9 us -34.6%
>
> The gain grows with the number of parameters, as expected, and short
> URIs get essentially nothing out of it. The same series built with -Og
> gives -6.2% on the large query, so that gain is not an artefact of one
> optimisation level.
>
> This is a pure optimization with no functional change, so the risk of
> regression is low. It is not needed in stable branches.
Nice, however I'm having a question here:
> @@ -449,13 +464,18 @@ enum uri_normalizer_err uri_normalizer_query_sort(const
> struct ist query, const
>
> while (istlen(scanner) > 0) {
> const struct ist param = istsplit(&scanner, delim);
> + const char *eq;
>
> if (param_count + 1 > max_param) {
> err = URI_NORMALIZER_ERR_ALLOC;
> goto fail;
> }
>
> - params[param_count] = param;
> + eq = memchr(istptr(param), '=', istlen(param));
> + params[param_count].ptr = istptr(param);
> + params[param_count].len = istlen(param);
> + params[param_count].name_len = eq ? (uint32_t)(eq -
> istptr(param))
> + : (uint32_t)istlen(param);
Did you try with a byte-by-byte approach instead of memchr() for
this one ? memchr() tends to be heavy for short strings since it
is usually fast thanks to vectorization, but parameter names are
almost always super short (1 or 2 chars), so I suspect you could
observe even further gainst using iststop() or something like this,
like was done before but admittedly not at an optimal place.
thanks,
Willy
