Buy commercial curl support from WolfSSL. We help you work
out your issues, debug your libcurl applications, use the API, port to new
platforms, add new features and more. With a team lead by the curl founder
himself.
Re: Getting a list of easy handles in a multi handle - possible?
- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]
From: Timothe Litt <litt_at_acm.org>
Date: Sat, 26 Aug 2023 16:19:07 -0400
On 26-Aug-23 15:12, Daniel Stenberg wrote:
> On Sat, 26 Aug 2023, Timothe Litt via curl-library wrote:
>
>> Not very efficient if there are lots of handles. You will scan the
>> list O(n^2) looking for prev each time - or, I suppose create a hash.
>
> Between each invoke there may be N new handles added and M handles may
> have been removed. How would the hash work?
>
What I meant here was a hash table on the side of (parallel to) your
existing list. Key is the handle, value is the corresponding list
index. When looking for "prev", you do an O(1) hash lookup to get its
index. Add 1, bounds check and return the next (or NULL).
You can add and delete items from a hash table as the list changes,
though depending on the hash table's structure it may be cheaper to
simply mark items deleted (e.g. index -1). To avoid compacting the
list on deletion (which would mean updating the hash values > the
deleted item), link unused entries into a freelist and hand them out
preferentially on a subsequent add.
Using an iterator as in my earlier note is a simpler solution to this
request - you look at the "next" slot in a copy of the list taken when
the iterator is created. Any subsequent add/delete isn't reflected. And
the bookkeeping is invisible to the caller. But to make it thread safe
(and to avoid the complications of intermediate add/deletes), you are
best off copying the list.
(Note that with your scheme, you're assuming that "prev" doesn't get
destroyed between calls.)
OTOH a hash table benefits all cases where you want to find an easy
handle in a multi handle. Keeping the existing list simplifies the
change and it's usually more efficient to walk a linear list than a hash
table for operations that want to iterate over the set.
The hash table does cost some memory, and depending on the
implementation there may be a cost to expand it beyond a
forecast/initial size.
Timothe Litt
ACM Distinguished Engineer
--------------------------
This communication may not represent the ACM or my employer's views,
if any, on the matters discussed.
Received on 2023-08-26
Date: Sat, 26 Aug 2023 16:19:07 -0400
On 26-Aug-23 15:12, Daniel Stenberg wrote:
> On Sat, 26 Aug 2023, Timothe Litt via curl-library wrote:
>
>> Not very efficient if there are lots of handles. You will scan the
>> list O(n^2) looking for prev each time - or, I suppose create a hash.
>
> Between each invoke there may be N new handles added and M handles may
> have been removed. How would the hash work?
>
What I meant here was a hash table on the side of (parallel to) your
existing list. Key is the handle, value is the corresponding list
index. When looking for "prev", you do an O(1) hash lookup to get its
index. Add 1, bounds check and return the next (or NULL).
You can add and delete items from a hash table as the list changes,
though depending on the hash table's structure it may be cheaper to
simply mark items deleted (e.g. index -1). To avoid compacting the
list on deletion (which would mean updating the hash values > the
deleted item), link unused entries into a freelist and hand them out
preferentially on a subsequent add.
Using an iterator as in my earlier note is a simpler solution to this
request - you look at the "next" slot in a copy of the list taken when
the iterator is created. Any subsequent add/delete isn't reflected. And
the bookkeeping is invisible to the caller. But to make it thread safe
(and to avoid the complications of intermediate add/deletes), you are
best off copying the list.
(Note that with your scheme, you're assuming that "prev" doesn't get
destroyed between calls.)
OTOH a hash table benefits all cases where you want to find an easy
handle in a multi handle. Keeping the existing list simplifies the
change and it's usually more efficient to walk a linear list than a hash
table for operations that want to iterate over the set.
The hash table does cost some memory, and depending on the
implementation there may be a cost to expand it beyond a
forecast/initial size.
Timothe Litt
ACM Distinguished Engineer
--------------------------
This communication may not represent the ACM or my employer's views,
if any, on the matters discussed.
-- Unsubscribe: https://lists.haxx.se/mailman/listinfo/curl-library Etiquette: https://curl.se/mail/etiquette.html
- application/pgp-signature attachment: OpenPGP digital signature