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

[Rémi Denis-Courmont]

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.

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.

> > 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.
> 
> 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.

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.

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).

> > > IIUC, you are saying that since there are trees, we don't need vectors?
> > 
> > No. I am saying that if you are concerned about element insertion and/or
> > deletion time, you really should not use an array to begin with, because
> > performance with an array will definitely suck.
> 
> I disagree. Other structures have their own drawbacks too. It depends on
> the concrete case.

You don't get to "disagree" with facts of computer science. Insertions and 
deletions in an array are at best linear, whether you like it or not.

> > 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.

-- 
Rémi Denis-Courmont