wxArrayString poor performance

[Eran Ifrah]

Hi,

As part of an overall code performance that I am conducting on CodeLite IDE

I was surprised to discover that one of the bottlenecks was wxArrayString

From my investigation, I noticed that the Add() method is the bottleneck

The code was spending considerably amount of time increasing the internal buffer.

For example, running this simple code:

#include <stdio.h>

#include <vector>

#include <wx/arrstr.h>

#include <wx/init.h>

int main(int argc, char** argv)

{

    wxInitializer init(argc, argv);

    wxArrayString arr;

    wxString str;

    str << "hello_World";

    for(size_t i = 0; i < 500000; ++i) {

        arr.push_back(str); // does not matter if I call here push_back() or Add()

    }

    return 0;

}

​Takes:

/home/eran

$time ./test_wxarr

real    0m0.823s

user    0m0.644s

sys     0m0.176s

These numbers are consistent.

This is how I ​compiled the sample program:

g++ test_wxarr.cpp -o test_wxarr `wx-config --cxxflags --libs` -std=c++11 -O2

​If I replace "wxArrayString" with: "std::vector<wxString>"

The numbers are improved dramatically:

/home/eran

$time ./test_v

real    0m0.065s

user    0m0.044s

sys     0m0.020s

My question:

Why don't we simply wrap std::vector<wxString> with wxArrayString? so basically wxArrayString is just an adapter to std::vector<wxString> ?

​BTW, for me, the workaround was: use std::vector<wxString> internally and then copy the content to wxArrayString. So the above code becomes:

#include <stdio.h>

#include <vector>

#include <wx/arrstr.h>

#include <wx/init.h>

#include <algorithm>

int main(int argc, char** argv)

{

    wxInitializer init(argc, argv);

    std::vector<wxString> v;

    wxString str;

    str << "hello_world";

    for(size_t i = 0; i < 500000; ++i) {

        v.push_back(str);

    }

    wxArrayString wxarr;

    wxarr.Alloc(v.size());

    std::for_each(v.begin(), v.end(), [&](const wxString& s){ wxarr.Add(s); });

    return 0;

}

And the numbers are now:

​/home/eran

$time ./test_v

real    0m0.087s

user    0m0.064s

sys     0m0.020s

​

​Still 1/10 of the time of running the same code with wxArrayString

What do you think?​

--

Eran Ifrah,
Author of CodeLite, a cross platform open source C/C++ IDE: http://www.codelite.org

CodeLite IDE Blog: http://codeliteide.blogspot.com/

[Igor Korot]

Hi,

On Fri, Nov 17, 2017 at 3:34 PM, Eran Ifrah <eran....@gmail.com> wrote:
> Hi,
>
> As part of an overall code performance that I am conducting on CodeLite IDE
> I was surprised to discover that one of the bottlenecks was wxArrayString
>
> From my investigation, I noticed that the Add() method is the bottleneck
> The code was spending considerably amount of time increasing the internal
> buffer.

If you are using C++11 why do you need wxArrayString?

Thank you.

> --
> To unsubscribe, send email to wx-dev+un...@googlegroups.com
> or visit http://groups.google.com/group/wx-dev
>

[Eran Ifrah]

Not that it is really matters, but many parts of CodeLite were written back in 2006 (*before* C++11)

Many API's in wxWidgets are using wxArrayString (wxChoice, wxListBox etc) it seems dumb to copy data back and forth from std::vector<wxString> (which predates c++11) to wxArrayString

I am sure that I am not the only one using wxArrayString... so the question is still valid

> --
> To unsubscribe, send email to wx-dev+unsubscribe@googlegroups.com
> or visit http://groups.google.com/group/wx-dev
>

--
To unsubscribe, send email to wx-dev+unsubscribe@googlegroups.com
or visit http://groups.google.com/group/wx-dev

[Eric Jensen]

Hello Eran,

Friday, November 17, 2017, 10:34:47 PM, you wrote:

EI> Hi,


EI> As part of an overall code performance that I am conducting on CodeLite IDE
EI> I was surprised to discover that one of the bottlenecks was wxArrayString


EI> From my investigation, I noticed that the Add() method is the bottleneck
EI> The code was spending considerably amount of time increasing the internal buffer.

If you know in advance how many elements you need, call
wxArrayString::Alloc()

Or set it to a (reasonable) big number and call
wxArrayString::Shrink() when you're done adding elements.

Eric

[Eran Ifrah]

Also note that the documentation speaks highly of this class.

http://docs.wxwidgets.org/3.1/classwx_array_string.html#a217ff3d3246ea5079bac9295ff36a237

If we are not going to fix this, at least, we should place a comment in the documentation stating that its performance is not anywhere close to std::vector<wxString> and std::vector<wxString> should be preferred over wxArrayString where possible

[Eran Ifrah]

On Sat, Nov 18, 2017 at 12:00 AM, Eric Jensen <m...@j-dev.de> wrote:

Hello Eran,

Friday, November 17, 2017, 10:34:47 PM, you wrote:

EI> Hi,


EI> As part of an overall code performance that I am conducting on CodeLite IDE
EI> I was surprised to discover that one of the bottlenecks was wxArrayString


EI> From my investigation, I noticed that the Add() method is the bottleneck
EI> The code was spending considerably amount of time increasing the internal buffer.

If you know in advance how many elements you need, call
wxArrayString::Alloc()

​If you look at the my initial email, you will see that in my workaround I am calling Alloc() in advance to the size of the vector

I know that this makes the difference, but std::vector gets much superior numbers compared to wxArrayString

Using Alloc() is not always possible: in many cases, I don't know the numbers of items in advance...

FYI:

std::vector is o(1) per push_back call (google: "push_back amortized time")

It does that by using constant to increase it memory.

For example: If you have 2 elements and you want to add 3rd element and the constant is 2, it will increase its size to 4 (2*2)

When you have 4 elements and you want to add the 5th element, it will first increase it's size to 8 etc

https://stackoverflow.com/questions/6550509/amortized-analysis-of-stdvector-insertion

Or set it to a (reasonable) big number and call
wxArrayString::Shrink() when you're done adding elements.

Eric

--
To unsubscribe, send email to wx-dev+unsubscribe@googlegroups.com
or visit http://groups.google.com/group/wx-dev

[Maarten Bent]

Some profiling results.

wxArrayString::Add
[65.8%] wxScopedArray<wxString> oldStrings(Grow(nInsert));
[33.1%] return ret;

Looking at wxArrayString::Grow
[12.1%] wxString *pNew = new wxString[m_nSize];
[0.2%] for ( size_t j = 0; j < m_nCount; j++ )
[53.4%] pNew[j] = m_pItems[j];

It looks like every time memory is allocated for wxArrayString, all the data is copied.
And the old array is destructed.

Maarten

[Teodor Petrov]

On 11/18/2017 04:24 AM, Maarten Bent wrote:
> Some profiling results.
>
> wxArrayString::Add
> [65.8%] wxScopedArray<wxString> oldStrings(Grow(nInsert));
> [33.1%] return ret;
>
> Looking at wxArrayString::Grow
> [12.1%] wxString *pNew = new wxString[m_nSize];
> [0.2%] for ( size_t j = 0; j < m_nCount; j++ )
> [53.4%] pNew[j] = m_pItems[j];
>
> It looks like every time memory is allocated for wxArrayString, all
> the data is copied.
> And the old array is destructed.

This is obviously inevitable. Probably you could redesign this using
moves, but it still won't fix the main problem.
And the main problem is that growing is done linearly and not in a
quadratic fashion. And worse there is a cap
on the max grow size - ARRAY_MAXSIZE_INCREMENT = 4096. So you cannot do
a manual resize from user
code like: array.Grow(array.size()*2);

/Teodor

[Maarten Bent]

It's not linear, the allocated size is increased with 0.5*m_nSize.
But ARRAY_MAXSIZE_INCREMENT is indeed the biggest problem.
Removing it has a big performance gain, making it perform on par with
std::vector.

Increasing the allocated size with 1*m_nSize or 2*m_nSize has additional
performance gains.

Maarten

[Vadim Zeitlin]

On Fri, 17 Nov 2017 23:34:47 +0200 Eran Ifrah wrote:

EI> As part of an overall code performance that I am conducting on CodeLite IDE
EI> I was surprised to discover that one of the bottlenecks was wxArrayString

Thanks for doing this, it was indeed unexpected to me too.

EI> From my investigation, I noticed that the Add() method is the bottleneck
EI> The code was spending considerably amount of time increasing the internal

EI> buffer.
EI>
EI>
EI> For example, running this simple code:
EI>
EI> #include <stdio.h>
EI> #include <vector>
EI> #include <wx/arrstr.h>
EI> #include <wx/init.h>
EI>
EI> int main(int argc, char** argv)
EI> {
EI> wxInitializer init(argc, argv);
EI> wxArrayString arr;
EI> wxString str;
EI> str << "hello_World";
EI> for(size_t i = 0; i < 500000; ++i) {
EI> arr.push_back(str); // does not matter if I call here push_back() or Add()
EI> }
EI> return 0;
EI> }

I've modified this to use wxStopWatch which is slightly more precise, but
I can still reproduce about the same numbers: with wxArrayString it takes
800ms, with std::vector -- 40ms.

EI> My question:
EI> Why don't we simply wrap std::vector<wxString> with wxArrayString?

This is done in wxUSE_STD_CONTAINERS build, which is enabled by wxUSE_STL
too and if there are no backwards compatibility concerns, it's a good idea
to use it. Unfortunately we still don't use it by default, but maybe we
should change this for 3.2...


On Sat, 18 Nov 2017 03:24:08 +0100 Maarten Bent wrote:

MB> Some profiling results.
MB>
MB> wxArrayString::Add
MB> [65.8%] wxScopedArray<wxString> oldStrings(Grow(nInsert));
MB> [33.1%] return ret;
MB>
MB> Looking at wxArrayString::Grow
MB> [12.1%] wxString *pNew = new wxString[m_nSize];
MB> [0.2%] for ( size_t j = 0; j < m_nCount; j++ )
MB> [53.4%] pNew[j] = m_pItems[j];
MB>
MB> It looks like every time memory is allocated for wxArrayString, all the
MB> data is copied.
MB> And the old array is destructed.

Thanks for taking time to profile it but, for once, the results are not
really surprising. This code basically does nothing else than allocating
memory in a loop, so of course the execution time is dominated by doing it
and copying data into the new buffer.

There are 2 possible optimizations here:

1. Use realloc() instead of new[] to avoid copying as much as possible.
wxVector<> does this, but the same benchmark shows that it's only
slightly faster than wxArrayString, so, clearly, we can't always grow
our memory pool in place.

2. Move strings to the new storage instead of copying them. I wouldn't
expect this to result in any big gains with this particular benchmark
because "hello_World" should fir in the internal string buffer, but
for longer strings this should be a big gain. Of course, it could only
be done in C++11 mode but this is not really an important constraint
nowadays.


On Sat, 18 Nov 2017 10:56:45 +0200 Teodor Petrov wrote:

TP> And the main problem is that growing is done linearly and not in a
TP> quadratic fashion. And worse there is a cap
TP> on the max grow size - ARRAY_MAXSIZE_INCREMENT = 4096.

Indeed, we're too conservative here. With the following patch:
---------------------------------- >8 --------------------------------------
diff --git a/src/common/arrstr.cpp b/src/common/arrstr.cpp
index ccc25f23ab..cd599f6b22 100644
--- a/src/common/arrstr.cpp
+++ b/src/common/arrstr.cpp
@@ -140,6 +140,7 @@ wxString *wxArrayString::Grow(size_t nIncrement)
return NULL;
}
else {
+#if 0
// otherwise when it's called for the first time, nIncrement would be 0
// and the array would never be expanded
// add 50% but not too much
@@ -150,6 +151,9 @@ wxString *wxArrayString::Grow(size_t nIncrement)
if ( nIncrement < ndefIncrement )
nIncrement = ndefIncrement;
m_nSize += nIncrement;
+#else
+ m_nSize *= 2;
+#endif

wxString *pNew = new wxString[m_nSize];

// copy data to new location
---------------------------------- >8 --------------------------------------
I get ~30ms on the benchmark, i.e. faster than std::vector<>. Of course,
the idea for not doing this from the beginning was to avoid consuming too
much RAM but maybe it's not such a good trade-off any more, even if it ever
was.

TP> So you cannot do a manual resize from user
TP> code like: array.Grow(array.size()*2);

This really shouldn't be necessary, if you know the size of your data in
advance (even approximately), calling reserve() is by far the fastest
solution, e.g. this benchmark takes ~8ms if I do this.

Regards,
VZ

[Vadim Zeitlin]

On Sat, 18 Nov 2017 13:07:25 +0100 Maarten Bent wrote:

MB> It's not linear, the allocated size is increased with 0.5*m_nSize.
MB> But ARRAY_MAXSIZE_INCREMENT is indeed the biggest problem.
MB> Removing it has a big performance gain, making it perform on par with
MB> std::vector.
MB>
MB> Increasing the allocated size with 1*m_nSize or 2*m_nSize has additional
MB> performance gains.

Indeed. But the really amazing thing is that using Massif to look at the
peak memory usage shows that, at least under Linux, using 2 as growth
factor results in using _less_ memory for this benchmark than the current
code and also less than 1.5 growth factor that would be used by
wxArrayString without the allocation size limit. I'm not sure why is it so,
my explanation is that all the intermediary allocations still belong to the
process and can't be reused when the buffer is being reallocated,
contributing to the increased peak heap usage. In more realistic
situations, where the application does something else than just allocating
memory for strings, this extra memory could presumably be used to hold
something else instead of being totally wasted, so it wouldn't be that bad,
but this is difficult to test.

For the reference, here are the results of my benchmarks under Linux
x86_64, where sizeof(wxString) == 24 and so 500000 of them should take 12MB
of RAM:

Growth strategy | Time (ms) | Peak heap (MB)
------------------------------+-----------+---------------
Current, with max alloc limit | ~830 | 24.0
std::vector (from libstdc++) | 32 | 19.0
Growth factor 1.5, no limit | 42 | 21.6
Growth factor 2, no limit | 29 | 19.0
Growth factor 3, no limit | 21 | 20.3
------------------------------+-----------+---------------

So it looks like 2x growth is a decent compromise (even though
https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md says
that it's the worst possible choice) and so I've just switched to it in
https://github.com/wxWidgets/wxWidgets/commit/ac052d60234680a4806609d6529e04e7622f8f31

The commit above is part of https://github.com/wxWidgets/wxWidgets/pull/606
which is, at least for me, much more important than this performance gain,
as it removes more than 1000 lines of legacy code by making all dynamic
arrays (including wxArrayString) use wxVector. I could be missing something
here (some incompatibility that we'll only discover after releasing
3.2.0?), but I see no reason not to do this: like this we reuse the same
code in both STL and non-STL builds and just have a single wxVector to
maintain, if this (I think we could drop it as well and just use
std::vector everywhere by now), instead of 2.5 different implementations.

Any comments about this PR would be welcome!
VZ

[Eran Ifrah]

Thanks for the PR, once this is committed to master, I will be more than happy to test it on a real world application (at least on Windows)

along with the wxSTC ligature fix (I think it is still in patch form on wxTrac, so I don't mind applying it locally)

Again, big thanks!

[digifuzzy]

On Saturday, 18 November 2017 05:19:13 UTC-7, VZ wrote:

On Fri, 17 Nov 2017 23:34:47 +0200 Eran Ifrah wrote:

EI> My question:
EI> Why don't we simply wrap std::vector<wxString> with wxArrayString?

 This is done in wxUSE_STD_CONTAINERS build, which is enabled by wxUSE_STL
too and if there are no backwards compatibility concerns, it's a good idea
to use it. Unfortunately we still don't use it by default, but maybe we
should change this for 3.2...

The funny thing about configure flags is that each distribution tends to have their own ideas about what to and not to use. Case in point, the difference in configure flags used between Fedora RPM spec file, Arch Linux PKGBUILD, and FreeBSD ports Makefile (not to mention all the patch files they each include!). The package maintainers probably have their reasons for these flags, but are they using "current" knowledge for this decision? I have had to re-evaluate a few things along the way as wxWidgets has evolved. Have the distribution maintainers?

This forces a person developing an application, intent on redistribution in the Open Source world, to either use the flags their distribution uses, or make alternate arrangements for wxWidgets libraries (possibly including building specialized wxWidgets libraries).

I'm not a wx maintainer, but using wxUSE_STL as default going forward would seem optimal to me - make use of underlying C++ container handling.
Would this not make code maintenance easier?

[Vadim Zeitlin]

On Sat, 18 Nov 2017 13:31:23 -0800 (PST) digifuzzy wrote:

d> The funny thing about configure flags is that each distribution tends to
d> have their own ideas about what to and not to use. Case in point, the
d> difference in configure flags used between Fedora RPM spec file
d> <https://apps.fedoraproject.org/packages/wxGTK3/sources/spec/>, Arch Linux
d> PKGBUILD
d> <https://git.archlinux.org/svntogit/packages.git/tree/trunk/PKGBUILD?h=packages/wxgtk>,
d> and FreeBSD ports Makefile
d> <https://svnweb.freebsd.org/ports/head/x11-toolkits/wxgtk30/Makefile?view=markup>

I'm not sure which difference exactly do you mean, I might be missing
something, but I don't see any important differences. It's just some of the
files above (unnecessarily but harmlessly) specify some flags that are
already on by default anyhow, and some use flags to tweak the build process
itself (e.g. disable dependencies tracking or PCH use), but they all still
mostly use default options which is just as it should be.

d> (not to mention all the patch files they each include!).

This is potentially more worrisome but we can just hope the maintainers of
these packages propagate their fixes back to us if appropriate. And at
least some of them definitely do this (thanks!).

d> I'm not a wx maintainer, but using wxUSE_STL as default going forward would
d> seem optimal to me - make use of underlying C++ container handling.
d> Would this not make code maintenance easier?

It would, but it would also break tons of (90%?) existing code because
there is no more conversion from wxString to "const char*" in the STL
build. There are other minor incompatibilities, but the real sticking point
is this one and I don't think it's going to change in wxWidgets 3. When
we'll be discussing wxWidgets 4, we could get back to it, but it's not
planned for the immediate future.

Regards,
VZ