[vlc-devel] [RFC 0/3] Improving vlc_array_t

[Romain Vimont]

On Sat, Jul 21, 2018 at 03:26:35PM +0300, Rémi Denis-Courmont wrote:
> Le samedi 21 juillet 2018, 14:35:23 EEST Romain Vimont a écrit :
> > > But in C, the normal way to handle vectors is a typed pointer and an
> > > unsigned counter (or an error-value terminator). And it turns out that
> > > VLC actually does that a lot - just not with the hopeless helpers.
> > 
> > I don't think that the helpers are hopeless.
> 
> I don't know that TAB_* is hopeless; there may be ways to fix error handling, 
> but it has proven elusive within the scope of standard C so far.

The obvious solution is to add a parameter to
{TAB,ARRAY}_{APPEND,INSERT}(), but it's not very user-friendly.

> However vlc_array_t is hopeless. By design, ti will never support non-pointer 
> elements and never provide type-safety. And given that C actually supports 
> type safety for arrays just fine (unlike complex data structures), that is 
> inexcusable.

I would like a vector-like/dynamic-array structure/API which exposes
basic functions (I didn't add them all in this RFC) with "standard"
behavior.

I started with vlc_array_t, because I thought it was the most
appropriate for storing pointers ("simple" API, can return a bool on
alloc errors). As you said, it has drawbacks and does not work for all
cases (non-pointers, type-safety).

IMO, this should not prevent to improve it. But I'm totally ok to also
add functions (reserve(), find(), swap_remove(), etc.) to ARRAY_*,
TAB_*, or whatever.

> > > But TBH, it is quite seldom that we do index-based random access. Usually,
> > > it's either sequential access or look-up by some key.

Random access is sometimes needed though. For example, for random
playing, selecting the next item involves swapping two items by index
(e.g. Fisher–Yates algorithm).

> > I start working on some playlist/shuffle stuff, and my first choice
> > is to use a vector-like tool. Maybe in the end, for some reason, I will
> > switch to another structure, but a vector-like API would still be useful
> > IMO.
> 
> An array is _not_ a good choice for the playlist given the large number of 
> potential items, and the fact that it sees potentially a lot of random 
> insertions and deletions.

What would you suggest for the playlist?

> At the time when the playlist code was written, there were no other data 
> structure helpers, but that is not an excuse for reproducing the same mistake 
> again. Besides, the array is primarily for looking up items by ID, something 
> that should go away in favor of proper reference counting.

Could you explain what you mean (replacing lookup by ID by reference
counting)?

> And contrary to your claims, this patchset does not make array insertion 
> constant. That is logically impossible. It only makes appending constant on 
> average (leaving it linear on worst case).

I said _amortized constant time_, like std::vector::push_back() for
instance. I said nothing about the worst case.

> > > Insertion and deletion in an array will always be linear (assuming that
> > > heap allocation is linear or less). The only thing you can hope to
> > > optimize is appending and tail deletion - and even then a LIFO is usually
> > > a better choice.
> > If order need not be preserved, deletion may be O(1) (swap_remove()).
> 
> The array helpers are for sorted arrays. You cannot just change them and break 
> that assumption.

No, they are not for _sorted_ arrays only (the items do not even have to
be comparable, unless for cases where BSEARCH is used). Of course, they
contain a sequence of items, in an order defined by the
insertions/deletions operations.

But the fact that this order is meaningful or not is defined by the
"client". If it is not meaningful, the client may prefer to remove using
swap_remove() to get deletion in O(1):
<https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap_remove>