On 4/02/2016 4:40 a.m., Alex Rousskov wrote: > On 02/03/2016 04:29 AM, Amos Jeffries wrote: > >>>>> Pipeline class is updated to use the ID number to manage its contents >>>>> rather than Pointer value matching. It is also updated to drop the >>>>> HTTP/1 specific assumptions within the Pipeline implementation. As a >>>>> behavioural requirement the sequential flow is now left for the Server >>>>> and ClientHttpRequest Jobs to ensure correctness. >>>> >>>> >>>> The new Pipeline::popById() method is a bad idea IMO: Linear search is >>>> wrong for both HTTP/1 and HTTP/2. >>>> >>> >>> Do you have a better algorithm? it needs to pop using only an ID (HTTP/2 >>> limit due to framing) and works on linear/list storage (optimal for >>> HTTP/1 sequentialism). > > I am sure I can create a solution, but I was hoping to avoid doing that. > I can start by suggesting that if what you are saying is true, then you > probably need to either
I mean algorithm, if you can name one I can look up that would be fine and I investigate using it as opposed to search. What I've used is the best I can think of so far. The use-case is to process a new HTTP/2 frame arriving and associate it to the stream. So a map might work, but would grow to perhapse 2^32 entries unless we could also find a good way to purge entries. With only a small / limited number active at any time the search/walk should be "fast enough" and is replaceable if that better algorithm appears tomorrow or next year. > > * configure Pipeline to use one of the two different storage structures > with the same API (optimal but often more difficult to design right) or > This is kind of the direction why I picked list as the type for Pipeline to begin with. std::queue is apparently implemented as a std::list with cutdown API in the first place. Going with just std::list then HTTP/1.x can use it as if it were a strict FIFO queue, while HTTP/2 can use it as a list very roughly "sorted" by priority (aka. FIFO but not a strict queue access ordering). Since the API type is a list, the Server class is made responsible for implementing the right semantics on the pipeline. For example; HTTP/1.x-only logics not doing a walk unless its by repeatedly pop()'ing, etc. > > For the first bullet, please note HTTP/1 can internally do a > simple/efficient "pop(void)" and only then check the popped ID, even > though its public API can be exactly the same "removeById()" API used by > HTTP/2. Sounds okay. I will look at adding that with version indicators in the method docs so we can see the dual-API separation and see how that goes. > * always use one Pipeline storage structure with two indices (worse > performance, more RAM, and messier code but possibly easier to shovel > into Squid). > > BTW, "Pipeline" does not sound like the right name for a class managing > mostly independent components each of which can be removed at any time > without significant effect on others (as is the case with HTTP/2 streams). "pipeline" is the RFC term for the set of transactions sent/received on a single connection, so I went with the flow. (pun intended, have a nice day). Amos _______________________________________________ squid-dev mailing list [email protected] http://lists.squid-cache.org/listinfo/squid-dev
