<html>
<head>
<base href="https://bugs.webkit.org/" />
</head>
<body>
<p>
<div>
<b><a class="bz_bug_link
bz_status_NEW "
title="NEW - Replace HTTPHeaderMap by HTTPHeaderList"
href="https://bugs.webkit.org/show_bug.cgi?id=152828#c3">Comment # 3</a>
on <a class="bz_bug_link
bz_status_NEW "
title="NEW - Replace HTTPHeaderMap by HTTPHeaderList"
href="https://bugs.webkit.org/show_bug.cgi?id=152828">bug 152828</a>
from <span class="vcard"><a class="email" href="mailto:achristensen@apple.com" title="Alex Christensen <achristensen@apple.com>"> <span class="fn">Alex Christensen</span></a>
</span></b>
<pre>(In reply to <a href="show_bug.cgi?id=152828#c2">comment #2</a>)
<span class="quote">> (In reply to <a href="show_bug.cgi?id=152828#c1">comment #1</a>)
> > We also need to keep information about the first header with each name so
> > that set, get, contains, etc. don't have to search the whole list every time
> > they are called.
>
> Keeping the first index would optimize the case of get and contains.
> set and remove would remain O(n), at least in a worst case scenario.
> It would also slow down append().</span >
We should also keep track of which headers only have one header in the list with the given name, so set and remove will be O(1) for headers with a unique name. Headers with a non-unique name will still be O(n), but remove needs to be O(n) anyways to update the structures.
<span class="quote">>
> I would first like to have a simple functional HTTPHeaderList with a clean
> API. Then it could be optimized internally to handle large sets.</span >
This would be a performance regression until the optimizations are done. I don't think we should do this.
<span class="quote">>
> For instance, keeping-first-index mechanism might be triggered when header
> set size is above a given threshold. </span >
This would make it hard to find bugs that only appear in large lists or near the threshold. I don't think we should do this. Optimizing for small lists is a premature optimization.
<span class="quote">> Or it can be done lazily when a header is actually get.</span >
This would make get slow.
Basically, we should not use data structures that assume that the number of headers will always stay small. This is a bad assumption unless you can verify that there is no important use of many headers on the entire internet.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are the assignee for the bug.</li>
</ul>
</body>
</html>