STL container performance

[cdm.he...@googlemail.com]

I am suffering performance problems with the STL implementation in
Microsoft Visual Studio 2005. There are indications that it is down to
either memory management or some locking contention.

As an example, the WordCount sample at http://craighenderson.co.uk/mapreduce/
running on a 100Mb text file executes in 1 minute 39 seconds when
compiled with the MSVC STL. Running the same program rebuilt against
STLPort 5.2 runs in only 20 seconds on the same dataset.

Is there any documentation about the performance characteristic of the
MSVC STL? Is this a known and acknowledged performance problem? Are
there any compilation options to boost performance?

I am very interested in getting the performance of STLPort out of the
compiler's supplied STL implementation.

Thanks
-- Craig

[Alex Blekhman]

<cdm.he...@googlemail.com> wrote:
> I am suffering performance problems with the STL implementation
> in Microsoft Visual Studio 2005. There are indications that it
> is down to either memory management or some locking contention.

You may observe checked iterators in action. Starting from
VC++2005 checked iterators are turned on by default. See more info
here:

"Checked Iterators"
http://msdn.microsoft.com/en-us/library/aa985965(VS.80).aspx

HTH
Alex

[Stephan T. Lavavej [MSFT]]

And they're off by default in VS 2010.

Stephan T. Lavavej
Visual C++ Libraries Developer

"Alex Blekhman" <tkfx....@yahoo.com> wrote in message
news:45922BEB-C3CF-40F5...@microsoft.com...

[Stephen Howe]

On Mon, 17 Aug 2009 14:29:03 -0700 (PDT),
"cdm.he...@googlemail.com" <cdm.he...@googlemail.com> wrote:

>I am suffering performance problems with the STL implementation in
>Microsoft Visual Studio 2005. There are indications that it is down to
>either memory management or some locking contention.

May be memory management.

STLPort has a nodal allocater (pooled memory?) which boosts
performance of std::list, std::set, std::map etc.

Out of the box, VS2005 does not. But you can buy a package of
allocators from Dinkumware that gives you the same thing.

Cheers

Stephen Howe

[cdm.he...@googlemail.com]

> You may observe checked iterators in action. Starting from
> VC++2005 checked iterators are turned on by default. See more info
> here:
>
> "Checked Iterators"http://msdn.microsoft.com/en-us/library/aa985965(VS.80).aspx
>
> HTH
> Alex

Thanks Alex. That got the runtime down to 56 seconds. Still a long way
of STLport performance, though.
-- Craig

[Stephan T. Lavavej [MSFT]]

And those allocators are included in VS 2010.

Stephan T. Lavavej
Visual C++ Libraries Developer

"Stephen Howe" <sjhoweATdialDOTpipexDOTcom> wrote in message
news:odll85tdlvpsut6cc...@4ax.com...

[Jeff Flinn]

And boost already has pool allocators that work with existing versions.
See http://www.boost.org/doc/libs/1_39_0/libs/pool/doc/index.html

Jeff

[Stephen Howe]

>And those allocators are included in VS 2010.
>
>Stephan T. Lavavej
>Visual C++ Libraries Developer

BTW, the assembly version of strlen() (and similar other strxxx())
functions are not as tight as they could be. They all special case bit
31 being set. It is not necessary. It is possible with the right
constants and expression to test all 4 bytes symmetrically.

Essentially you want

((z - 0x01010101) & ~z & 0x80808080) if z is an integer.
It will be zero if no byte is zero and the byte in question 80 if zero
to start with. Considering strlen() is one of those routines used
everywhere, it should be made tighter.

I see

main_loop:
mov eax,dword ptr [ecx] ; read 4 bytes
mov edx,7efefeffh
add edx,eax
xor eax,-1
xor eax,edx
add ecx,4
test eax,81010100h
je short main_loop
; found zero byte in the loop
mov eax,[ecx - 4]
test al,al ; is it byte 0
je short byte_0
test ah,ah ; is it byte 1
je short byte_1
test eax,00ff0000h ; is it byte 2
je short byte_2
test eax,0ff000000h ; is it byte 3
je short byte_3
jmp short main_loop ; taken if bits 24-30 are
clear and bit
; 31 is set

This "bit 31" business is suboptimal
There is absolutely no need to special case it and have an extra jmp

main_loop:
mov eax,dword ptr [ecx] ; read 4 bytes
add ecx,4
mov edx,eax
not eax
sub edx,01010101h
and eax,80808080h
and eax,edx
je short main_loop
; found zero byte in the loop
mov eax,[ecx - 4]
test al,al ; is it byte 0
jne short byte_0
test ah,ah ; is it byte 1
jne short byte_1
test eax,00ff0000h ; is it byte 2
jne short byte_2
; fall through, must be byte 3

str_misaligned should also be somewhere else.
The code should presume that strings are naturally aligned and fall
into the main loop. str_misaligned should happen but the code should
jump back to main loop once aligned (so misaligned strings pay a jump
penalty, aligned strings pay no jump penalty).

memchr()
strcat()
strchr()
strlen()
strncat()
strncpy()

all have this.

Stephen Howe

[youdahe]

I am interested in the solution as well, we have an application heavily depends on stl containers, we rebuilt the app using VC10 and native STL (was using stlport) and the performance goes down badly. (100% to 300% slower), is there something we need to know to turn the performance up?

cdm.henderso wrote:

Thanks Alex. That got the runtime down to 56 seconds.

26-Oct-09

Thanks Alex. That got the runtime down to 56 seconds. Still a long way
of STLport performance, though.
-- Craig

Previous Posts In This Thread:

On Monday, August 17, 2009 8:36 PM

Stephan T. Lavavej [MSFT] wrote:

And they are off by default in VS 2010.Stephan T.
And they are off by default in VS 2010.

Stephan T. Lavavej
Visual C++ Libraries Developer

On Tuesday, August 18, 2009 12:34 PM
Stephen Howe wrote:

May be memory management.STLPort has a nodal allocater (pooled memory?
May be memory management.

STLPort has a nodal allocater (pooled memory?) which boosts
performance of std::list, std::set, std::map etc.

Out of the box, VS2005 does not. But you can buy a package of
allocators from Dinkumware that gives you the same thing.

Cheers

Stephen Howe

On Tuesday, August 18, 2009 4:24 PM

Stephan T. Lavavej [MSFT] wrote:

And those allocators are included in VS 2010.Stephan T.
And those allocators are included in VS 2010.

Stephan T. Lavavej
Visual C++ Libraries Developer

"Stephen Howe" <sjhoweATdialDOTpipexDOTcom> wrote in message

On Tuesday, August 18, 2009 6:00 PM
Alex Blekhman wrote:

You may observe checked iterators in action.
You may observe checked iterators in action. Starting from
VC++2005 checked iterators are turned on by default. See more info
here:

"Checked Iterators"
http://msdn.microsoft.com/en-us/library/aa985965(VS.80).aspx

HTH
Alex

On Wednesday, August 19, 2009 8:38 AM
Jeff Flinn wrote:

And boost already has pool allocators that work with existing versions.
And boost already has pool allocators that work with existing versions.
See http://www.boost.org/doc/libs/1_39_0/libs/pool/doc/index.html

Jeff

Stephan T. Lavavej [MSFT] wrote:

On Wednesday, August 19, 2009 6:32 PM
Stephen Howe wrote:

Essentially you want

I see

all have this.

Stephen Howe

On Monday, October 26, 2009 8:26 PM
cdm.henderso wrote:

STL container performance

I am suffering performance problems with the STL implementation in
Microsoft Visual Studio 2005. There are indications that it is down to
either memory management or some locking contention.

As an example, the WordCount sample at http://craighenderson.co.uk/mapreduce/

running on a 100Mb text file executes in 1 minute 39 seconds when
compiled with the MSVC STL. Running the same program rebuilt against
STLPort 5.2 runs in only 20 seconds on the same dataset.

Is there any documentation about the performance characteristic of the
MSVC STL? Is this a known and acknowledged performance problem? Are
there any compilation options to boost performance?

I am very interested in getting the performance of STLPort out of the
compiler's supplied STL implementation.

Thanks
-- Craig

On Monday, October 26, 2009 8:26 PM
cdm.henderso wrote:

Thanks Alex. That got the runtime down to 56 seconds.
Thanks Alex. That got the runtime down to 56 seconds. Still a long way
of STLport performance, though.
-- Craig

Submitted via EggHeadCafe - Software Developer Portal of Choice
DataContractSerializer Basics
http://www.eggheadcafe.com/tutorials/aspnet/ad947ce6-cd3e-4647-b69c-94d2f3b1b265/datacontractserializer-ba.aspx

[youdahe]

we have a application heavily depends on stl, as recently rebuilt the app using VC10, and the native ST: (was using stlport 5.2), the performance drops a lot, would like to knoe all of the tricks to improve the STL performance.

cdm.henderso wrote:

Thanks Alex. That got the runtime down to 56 seconds.

26-Oct-09

Thanks Alex. That got the runtime down to 56 seconds. Still a long way
of STLport performance, though.
-- Craig

Previous Posts In This Thread:

Cheers

Stephen Howe

You may observe checked iterators in action.
You may observe checked iterators in action. Starting from
VC++2005 checked iterators are turned on by default. See more info
here:

"Checked Iterators"
http://msdn.microsoft.com/en-us/library/aa985965(VS.80).aspx

HTH
Alex

On Wednesday, August 19, 2009 8:38 AM
Jeff Flinn wrote:

Jeff

Essentially you want

I see

all have this.

Stephen Howe

Thanks
-- Craig

Thanks Alex. That got the runtime down to 56 seconds.
Thanks Alex. That got the runtime down to 56 seconds. Still a long way
of STLport performance, though.
-- Craig

On Friday, March 05, 2010 1:19 AM
youda he wrote:

What is the fix?

I am interested in the solution as well, we have an application heavily depends on stl containers, we rebuilt the app using VC10 and native STL (was using stlport) and the performance goes down badly. (100% to 300% slower), is there something we need to know to turn the performance up?

Submitted via EggHeadCafe - Software Developer Portal of Choice

Sending SMTP email from within BizTalk Orchestration
http://www.eggheadcafe.com/tutorials/aspnet/9dd0f346-baf9-4674-a50f-1716445b26bc/sending-smtp-email-from-w.aspx

[Tom Widmer]

youda he wrote:
> we have a application heavily depends on stl, as recently rebuilt the app using VC10, and the native ST: (was using stlport 5.2), the performance drops a lot, would like to knoe all of the tricks to improve the STL performance.

Configuring node-based containers (like list, map and set) to use a pool
allocator will help a lot. Instead of:
std::list<int> mylist
you want:
std::list<int, fast_pool_allocator<int> >

http://www.boost.org/doc/libs/1_42_0/libs/pool/doc/index.html

Tom