QList in-array item size

[Thiago Macieira]

Hello

Currently QList is an array of void* and it stores items that fit that size and
are movable in the array itself. This has a couple of inefficiencies:

- on a 64-bit platform, there's a 50% overhead for QList<int>
(QList<short> and QList<char> are unlikely)

- QList<double> uses indirect allocation on 32-bit platforms

- QVariant has one member of 12 bytes on all platforms, QSharedPointer and
QWeakPointer are always twice the size of void*, so QList of them always
uses indirect allocation (including QVariantList)

So I'd like to propose a change to QList's allocation strategy.

Option 1: large > 2*sizeof(void*)
- pros: will include double, QSharedPointer and QWeakPointer
- cons: does not include QVariant on 32-bit platforms, 75% overhead on int on
32-bit

Option 2: large > 16 bytes
- pros: includes double, the pointers and QVariant
- cons: overhead of 75% of int and pointers on 32-bit; 50% overhead of
pointers on 64-bit

Option 3: make it QList<T> be an actual QVector<T> for movable types, maybe
with an upper limit of size (32 bytes, 128 bytes?).
- pros: suitable for all types, shares code
- cons: more complex to implement, more code to compile and parse in headers

One big difference between QList and QVector today is that QList has prepend /
takeFirst optimisation, whereas QVector must move all elements to accommodate.
I would prefer if that optimisation remained present.

[Olivier Goffart]

On Sunday 16 October 2011 16:21:40 Thiago Macieira wrote:
[...]

Post by Thiago Macieira
Option 3: make it QList<T> be an actual QVector<T> for movable types, maybe
with an upper limit of size (32 bytes, 128 bytes?).
- pros: suitable for all types, shares code
- cons: more complex to implement, more code to compile and parse in headers

This is the obvious solutions...

Post by Thiago Macieira
One big difference between QList and QVector today is that QList has prepend
/ takeFirst optimisation, whereas QVector must move all elements to
accommodate. I would prefer if that optimisation remained present.

It has to (it enable QList to be used for queue like data structure (and it
is, see QQueue)

QList was also supposed to expands to less code (than QVector) (at least that
is what Jasmin used to advertise some years ago)

[Thiago Macieira]

Post by Olivier Goffart

Post by Thiago Macieira
One big difference between QList and QVector today is that QList has
prepend / takeFirst optimisation, whereas QVector must move all elements
to accommodate. I would prefer if that optimisation remained present.

It has to (it enable QList to be used for queue like data structure (and it
is, see QQueue)
QList was also supposed to expands to less code (than QVector) (at least
that is what Jasmin used to advertise some years ago)

I don't see how it can expand to less code than a simple vector. The best case
scenario is to expand to the same code or to similar complexity -- assuming of
course that QVector is optimised to produce minimal code too.

[Olivier Goffart]

Post by Thiago Macieira

Post by Olivier Goffart

Post by Thiago Macieira
One big difference between QList and QVector today is that QList has
prepend / takeFirst optimisation, whereas QVector must move all
elements to accommodate. I would prefer if that optimisation
remained present.>

It has to (it enable QList to be used for queue like data structure (and
it is, see QQueue)
QList was also supposed to expands to less code (than QVector) (at least
that is what Jasmin used to advertise some years ago)

I don't see how it can expand to less code than a simple vector. The best
case scenario is to expand to the same code or to similar complexity --
assuming of course that QVector is optimised to produce minimal code too.

Because QList make use of much more stuff in QListData that is not template
type (hence, not generated for every types)
However, I beleive it is possible to do the same optimisation for movable type
within QVector, if we want to.

[Thiago Macieira]

Post by Olivier Goffart

Post by Thiago Macieira
I don't see how it can expand to less code than a simple vector. The best
case scenario is to expand to the same code or to similar complexity --
assuming of course that QVector is optimised to produce minimal code too.

Because QList make use of much more stuff in QListData that is not template
type (hence, not generated for every types)
However, I beleive it is possible to do the same optimisation for movable
type within QVector, if we want to.

The biggest difference between current QList and QVector is that the size of
the element is constant in QList, whereas it varies in QVector. The static
code to manage the array, however, need not know the difference: it only needs
to know the total size and the alignment requirement.

[l***@nokia.com]

Post by Olivier Goffart
[...]

Post by Thiago Macieira
Option 3: make it QList<T> be an actual QVector<T> for movable types, maybe
with an upper limit of size (32 bytes, 128 bytes?).
- pros: suitable for all types, shares code
- cons: more complex to implement, more code to compile and parse in headers

This is the obvious solutions...

Yes, I'd be in favor of this solution as well. But it is the one that
requires most work. I'm not sure it would be exactly a QVector<T>, but the
data layout should be similar (ie. inline data). Hard to say what the
upper size limit should be, as it depends on the usage pattern. Somewhere
between 16 and 128 bytes sounds correct though.

Cheers,
Lars

Post by Olivier Goffart

Post by Thiago Macieira
One big difference between QList and QVector today is that QList has prepend
/ takeFirst optimisation, whereas QVector must move all elements to
accommodate. I would prefer if that optimisation remained present.

It has to (it enable QList to be used for queue like data structure (and it
is, see QQueue)
QList was also supposed to expands to less code (than QVector) (at least that
is what Jasmin used to advertise some years ago)
_______________________________________________
Qt5-feedback mailing list
http://lists.qt.nokia.com/mailman/listinfo/qt5-feedback

[João Abecasis]

Post by Thiago Macieira
So I'd like to propose a change to QList's allocation strategy.
Option 1: large > 2*sizeof(void*)
- pros: will include double, QSharedPointer and QWeakPointer
- cons: does not include QVariant on 32-bit platforms, 75% overhead on int on
32-bit
Option 2: large > 16 bytes
- pros: includes double, the pointers and QVariant
- cons: overhead of 75% of int and pointers on 32-bit; 50% overhead of
pointers on 64-bit
Option 3: make it QList<T> be an actual QVector<T> for movable types, maybe
with an upper limit of size (32 bytes, 128 bytes?).
- pros: suitable for all types, shares code
- cons: more complex to implement, more code to compile and parse in headers

Option 4: Move the decision out of QList<T>, so that there's a default policy does what we want for the types you mention, but we still allow users pick the behaviour for their own types. This would also allow us to tweak the strategy for future types.

Cheers,


João

[Thiago Macieira]

Post by João Abecasis

Post by Thiago Macieira
Option 3: make it QList<T> be an actual QVector<T> for movable types, maybe
with an upper limit of size (32 bytes, 128 bytes?).
- pros: suitable for all types, shares code
- cons: more complex to implement, more code to compile and parse in headers

Option 4: Move the decision out of QList<T>, so that there's a default
policy does what we want for the types you mention, but we still allow
users pick the behaviour for their own types. This would also allow us to
tweak the strategy for future types.

I don't like the idea of having extra template parameters to our container
classes. That makes forward-declaring them more difficult and it creates the
problem that SCARY iterators is trying to solve in STL (post-C++11).

The other option is to have a traits class that is automatically used, like
QTypeInfo. That is more amenable. We just have to remember that for a given
QList<T> used in Qt 5.0, the allocation strategy cannot change until Qt 6.0.
We can only change the rules for new types T that weren't used in previous Qt
versions.

Anyway, I think the best option is that QList<T> become a simple wrapper over
either QVector<T> or QVector<T *>, adapting the API, and I think we agree on
that.

It only remains to be seen how to make the selection.

[João Abecasis]

Post by Thiago Macieira

Post by João Abecasis

Post by Thiago Macieira
Option 3: make it QList<T> be an actual QVector<T> for movable types, maybe
with an upper limit of size (32 bytes, 128 bytes?).
- pros: suitable for all types, shares code
- cons: more complex to implement, more code to compile and parse in headers

Option 4: Move the decision out of QList<T>, so that there's a default
policy does what we want for the types you mention, but we still allow
users pick the behaviour for their own types. This would also allow us to
tweak the strategy for future types.

I don't like the idea of having extra template parameters to our container
classes. That makes forward-declaring them more difficult and it creates the
problem that SCARY iterators is trying to solve in STL (post-C++11).

I didn't suggest this.

Post by Thiago Macieira
The other option is to have a traits class that is automatically used, like
QTypeInfo. That is more amenable. We just have to remember that for a given
QList<T> used in Qt 5.0, the allocation strategy cannot change until Qt 6.0.
We can only change the rules for new types T that weren't used in previous Qt
versions.

This is more like what I had in mind.

Post by Thiago Macieira
Anyway, I think the best option is that QList<T> become a simple wrapper over
either QVector<T> or QVector<T *>, adapting the API, and I think we agree on
that.

If we take this idea further, we could even remove QList from the ABI, in the sense that it would be a convenience wrapper or templated typedef... QVector<T> and QVector<T *> would be the types popping up in function signatures (documentation should probably still show QList<T>, though).

I wonder if that would reduce our code footprint in any way.

Post by Thiago Macieira
It only remains to be seen how to make the selection.

Qt5ABI::QListAllocationPolicy<T> :-p


João

[Oswald Buddenhagen]

Post by l***@nokia.com

Post by Olivier Goffart

Post by Thiago Macieira
Option 3: make it QList<T> be an actual QVector<T> for movable types,

This is the obvious solutions...

Yes, I'd be in favor of this solution as well. But it is the one that
requires most work.

i think rittk has already done half of it. i've been discussing this
matter with him for half a year now.

Post by l***@nokia.com

Post by Olivier Goffart
Option 4: Move the decision out of QList<T>, so that there's a default
policy does what we want for the types you mention, but we still allow
users pick the behaviour for their own types. This would also allow us to
tweak the strategy for future types.

I don't like the idea of having extra template parameters to our container
classes. That makes forward-declaring them more difficult and it creates the
problem that SCARY iterators is trying to solve in STL (post-C++11).
The other option is to have a traits class that is automatically used, like
QTypeInfo. That is more amenable.

well, i consider that self-evident. i would just make Q_DECLARE_TYPEINFO
for Q_LARGE_TYPE completely explicit.

[l***@nokia.com]

On 10/17/11 1:35 PM, "ext Oswald Buddenhagen"

Post by Oswald Buddenhagen

Post by l***@nokia.com

Post by Olivier Goffart

Post by Thiago Macieira
Option 3: make it QList<T> be an actual QVector<T> for movable types,

This is the obvious solutions...

Yes, I'd be in favor of this solution as well. But it is the one that
requires most work.

i think rittk has already done half of it. i've been discussing this
matter with him for half a year now.

Post by l***@nokia.com

Post by Olivier Goffart
Option 4: Move the decision out of QList<T>, so that there's a default
policy does what we want for the types you mention, but we still allow
users pick the behaviour for their own types. This would also allow

us to

Post by Olivier Goffart
tweak the strategy for future types.

I don't like the idea of having extra template parameters to our container
classes. That makes forward-declaring them more difficult and it creates the
problem that SCARY iterators is trying to solve in STL (post-C++11).
The other option is to have a traits class that is automatically used, like
QTypeInfo. That is more amenable.

well, i consider that self-evident. i would just make Q_DECLARE_TYPEINFO
for Q_LARGE_TYPE completely explicit.

Being able to change it is ok, but I do thing having a reasonable default
is valuable. Otherwise everything's large by default, which would IMO lead
to rather bad characteristics for simple&small user defined classes.

Lars

[Oswald Buddenhagen]

Post by l***@nokia.com

i would just make Q_DECLARE_TYPEINFO for Q_LARGE_TYPE completely
explicit.

Being able to change it is ok, but I do thing having a reasonable
default is valuable.

the value for "reasonable" varies wildly between usage patterns:
appending/prepending often benefits from in-array allocation (saved
allocs/frees), while insertion/removal in the middle of a big list
benefits from out-of-array allocation (smaller memmoves; but then, if
this becomes a problem, you probably have the wrong data structure
anyway).

Post by l***@nokia.com
Otherwise everything's large by default, which would IMO lead to
rather bad characteristics for simple&small user defined classes.

default to small. error out if the type is not primitive/movable.

[l***@nokia.com]

On 10/17/11 6:43 PM, "ext Oswald Buddenhagen"

Post by Oswald Buddenhagen

Post by l***@nokia.com
On 10/17/11 1:35 PM, "ext Oswald Buddenhagen"

i would just make Q_DECLARE_TYPEINFO for Q_LARGE_TYPE completely
explicit.

Being able to change it is ok, but I do thing having a reasonable
default is valuable.

appending/prepending often benefits from in-array allocation (saved
allocs/frees), while insertion/removal in the middle of a big list
benefits from out-of-array allocation (smaller memmoves; but then, if
this becomes a problem, you probably have the wrong data structure
anyway).

Post by l***@nokia.com
Otherwise everything's large by default, which would IMO lead to
rather bad characteristics for simple&small user defined classes.

default to small. error out if the type is not primitive/movable.

Bad idea. Most developers don't even know about our trait system, and
neither should they. I can already imagine all the questions and bug
reports we would get because of this.

Lars

[Oswald Buddenhagen]

Post by l***@nokia.com

Post by Oswald Buddenhagen

Post by l***@nokia.com
Otherwise everything's large by default, which would IMO lead to
rather bad characteristics for simple&small user defined classes.

default to small. error out if the type is not primitive/movable.

Bad idea. Most developers don't even know about our trait system,

yes, and that's a major source of performance problems, including in our
own code.

but whatever. the alternative is behaving just like a vector, i.e.,
erroring out if no copy c'tor can be found. in the vast majority of
cases performance doesn't matter anyway, and in the majority of the
remaining cases defaulting to vector-like behavior is typically the
performance-wise better, and most of all more expected choice. for POD
types, a clever compiler could even optimize a copy c'tor loop into a
memmove without us doing it explicitly based on qt typetraits.