Re: [PATCH 07/40] util: Add helpers for auto-freeing GSList filled with strings
On 2/9/21 3:48 PM, Peter Krempa wrote:
On Tue, Feb 09, 2021 at 15:22:40 +0100, Michal Privoznik wrote:
> On 2/6/21 9:32 AM, Peter Krempa wrote:
>> glib's 'g_autoslist()' doesn't support lists of 'char *'
strings. Add a
>> type alias 'virGSListString' so that we can register an
'autoptr'
>> function for it for simple usage of GSList with strings.
>>
>> Signed-off-by: Peter Krempa <pkrempa(a)redhat.com>
>> ---
>> src/libvirt_private.syms | 4 ++++
>> src/util/meson.build | 1 +
>> src/util/virglibutil.c | 27 +++++++++++++++++++++++++++
>> src/util/virglibutil.h | 28 ++++++++++++++++++++++++++++
>> 4 files changed, 60 insertions(+)
>> create mode 100644 src/util/virglibutil.c
>> create mode 100644 src/util/virglibutil.h
>>
>
>
>> diff --git a/src/util/virglibutil.h b/src/util/virglibutil.h
>> new file mode 100644
>> index 0000000000..2bff69f22f
>> --- /dev/null
>> +++ b/src/util/virglibutil.h
>> @@ -0,0 +1,28 @@
>> +/*
>> + * virglibutil.h: Utilities helping with glib usage
>> + *
>> + * This library is free software; you can redistribute it and/or
>> + * modify it under the terms of the GNU Lesser General Public
>> + * License as published by the Free Software Foundation; either
>> + * version 2.1 of the License, or (at your option) any later version.
>> + *
>> + * This library is distributed in the hope that it will be useful,
>> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
>> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
>> + * Lesser General Public License for more details.
>> + *
>> + * You should have received a copy of the GNU Lesser General Public
>> + * License along with this library. If not, see
>> + * <http://www.gnu.org/licenses/>;.
>> + */
>> +
>> +#pragma once
>> +
>> +#include "internal.h"
>> +
>> +void
>> +virGSListStringFree(GSList *l);
>> +
>> +typedef GSList virGSListString;
>
> So, GSList is a singly linked list. This doubles memory usage because for
> every string we have to also store pointer to next. Is O(n^2) that bad so
> that we have to sacrifice memory complexity?
Firstly, for any cases where we know the number of elements or at least
a sane upper bound before inserting, we still keep using a char **.
This leaves us with places that don't know how many elements there will
be which insert:
1) a lot of elements -> definitely worth the overhead
2) a few elements -> the overhead is comparatively small
Yeah, this is my assumption (based in my experience with small
machines), that we usually have very few items on string lists (thinking
of namespace code, cgroup code and likes).
In places we might want to care about memory complexity, the code can
use a char ** list with a counter variable instead of the GSList to
avoid both memory and computational complexity, but not memory
fragmentation issues where a (singly) linked list prevents memory copy
when enlarging.
Yeah. I guess I'm more fan of arrays then lists because arrays are more
cache friendly than linked lists.
Or alternatively even use 2 additional size variables, see VIR_RESIZE_N
to avoid reallocations for maximum optimization.
Hopefully we don't care about performance that much.
<rant>I am also not fan of glib. That may be another reason that I
prefer our own implementation. It suits our needs better.</rant>
Michal