Sunday, November 15, 2020

Digest for comp.lang.c++@googlegroups.com - 12 updates in 3 topics

Philipp Klaus Krause <pkk@spth.de>: Nov 15 05:14PM +0100

Hello. I've used C++ once in a while for a long time, but I'm not an expert.
 
I std::sort an std::vector of structs. The struct has a member function
used as comparison for the std::sort (it iterates through a subset fo
the entries in an std::valarray<bool> and return a value depending ont hat).
 
valgrind --tool=callgrind tells me that this std::sort contributes
significantly to the runtime of a function I want to make faster. I also
see that most of the runtime of the std::sort is spent inside operator
delete(void *) and operator new(unsigned long). For about 4000 calls to
std::sort I see about 90000 calls to delete and new each.
Why does std::sort need to allocate and deallocate memory that often?
Can I do something about it? What can I do to speed up this std::sort?
 
Philipp
 
P.S.: In
https://sourceforge.net/p/sdcc/code/HEAD/tree/branches/lospre-vs-mcpre/sdcc/src/SDCClospre.hpp,
the compare function is in lines 55-69, the calls to sort are in lines
224, 291 and 292.
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Nov 15 04:45PM

On 15/11/2020 16:14, Philipp Klaus Krause wrote:
> https://sourceforge.net/p/sdcc/code/HEAD/tree/branches/lospre-vs-mcpre/sdcc/src/SDCClospre.hpp,
> the compare function is in lines 55-69, the calls to sort are in lines
> 224, 291 and 292.
 
What makes you think std::sort is allocating memory as opposed to the elements being sorted?
 
/Flibble
 
--
¬
Bonita Montero <Bonita.Montero@gmail.com>: Nov 15 05:45PM +0100

std::sort shouldn't allocate memory by itself because it usually
uses quicksort, which is an in-place sort. It even hasn't an allo-
caor-parameter. It might be that the items you sort allocate and
deallocate memory when being moved / copied.
The allocation-method which usually allocates memory is stable_sort,
which usually uses mergesort.
Philipp Klaus Krause <pkk@spth.de>: Nov 15 06:11PM +0100

Am 15.11.20 um 17:45 schrieb Bonita Montero:
> uses quicksort, which is an in-place sort. It even hasn't an allo-
> caor-parameter. It might be that the items you sort allocate and
> deallocate memory when being moved / copied.
 
Hm, "moveed". Apparently C++ has something called move constructors. And
sometimes the compiler creates them automatically. Of course, I have no
idea if the compiler created move constructors here, or if I should
provide one or if move constructors are even relevant to my problem of
speeding up the std::sort.
 
The things being sorted (lines 50 to 69 of
https://sourceforge.net/p/sdcc/code/HEAD/tree/branches/lospre-vs-mcpre/sdcc/src/SDCClospre.hpp)
are structs containing three members: An boost::tuple<float, float>, an
std::valarray<bool> and a comparison function.
 
Philipp
Philipp Klaus Krause <pkk@spth.de>: Nov 15 06:32PM +0100

Am 15.11.20 um 17:45 schrieb Mr Flibble:
 
> What makes you think std::sort is allocating memory as opposed to the
> elements being sorted?
 
> /Flibble
 
Well, I know my compare function doesn't allocate memory, and valgrind
shows me that somehow through std::sort there are calls to delete and new.
My background is mostly C. If I'd see calls to malloc and free that
somehow happens through qsort, and my compare functions doesn't allocate
memory, it must be qsort.
 
Maybe I should just try to replace the std::sort by qsort to get rid of
the memory allocation stuff?
 
Philipp
Richard Damon <Richard@Damon-Family.org>: Nov 15 01:06PM -0500

On 11/15/20 12:32 PM, Philipp Klaus Krause wrote:
 
> Maybe I should just try to replace the std::sort by qsort to get rid of
> the memory allocation stuff?
 
> Philipp
 
One thing to take a close look at is what you are actually sorting.
These will need to be moved from one place to another, and this might be
done using placement-new/move-constructors, which might LOOK like memory
allocation, or the classes move-constructor might be falling back to a
copy constructor and allocating memory.
 
qsort, since it moves with memcpy isn't suitable for sorting 'object'
that have constructors, but only pointers to them. This also points to
the fact that sorting an array of pointers will also be quicker to do in
many cases to sorting the objects themselves (if the objects have
significant size), but does cost and additional indirection and might be
a bit less cache friendly.
Philipp Klaus Krause <pkk@spth.de>: Nov 15 07:32PM +0100

Am 15.11.20 um 19:06 schrieb Richard Damon:
> many cases to sorting the objects themselves (if the objects have
> significant size), but does cost and additional indirection and might be
> a bit less cache friendly.
 
I just did a quick test comparing std::sort to qsort by sorting an
std::vector of 1000 of these:
 
#define GLOBAL_SIZE 5
 
struct s
{
boost::tuple<float, float> s;
std::valarray<bool> global;
int size;

bool operator <(const struct s& s) const
{
for(int i = 0; i < GLOBAL_SIZE; i++)
{
if (global[i] < s.global[i])
return(true);
if (global[i] > s.global[i])
return(false);
}
return(false);
}
};
 
std::sort took about 2.5 times as long as qsort. So I guess the bottom
line is that std::sort can be fast (as can be seen from various websites
where people claim that std::sort is faster than qsort by sorting arrays
of ints or floats), but for anything nontrivial to be sorted, will take
extra work to do so.
 
Any recommendatiosn on what I need to do to get fast sorting? Write a
move constructor? Write a custom swap function? Anything else?
https://stackoverflow.com/questions/14212701/stdsort-does-not-always-call-stdswap
looks like there are multiple things to implement just to get efficient
sorting.
David Brown <david.brown@hesbynett.no>: Nov 15 08:06PM +0100

On 15/11/2020 19:32, Philipp Klaus Krause wrote:
> where people claim that std::sort is faster than qsort by sorting arrays
> of ints or floats), but for anything nontrivial to be sorted, will take
> extra work to do so.
 
Your structure here has non-trivial constructors and destructors - it
contains a "valarray" which is a dynamically allocated array. Each time
the sort algorithm needs to move these "struct s" structures around,
it's going to have to create and destroy them.
 
As it stands, this is the only correct way to do it - movement using
memcpy may be invalid. C-style "qsort" can only beat std::sort because
it ignores the requirements of the C class.
 
> https://stackoverflow.com/questions/14212701/stdsort-does-not-always-call-stdswap
> looks like there are multiple things to implement just to get efficient
> sorting.
 
Custom swap and move constructors are definitely a help here. Another
obvious choice is that you should not use "valarray" when you know the
size of the array - use "std::array" which has the convenience of
working like a C++ container, but the efficiency of a fixed-size C array.
 
You should also consider whether you want an array here at all. The
code you have presented might be a simplification, but it is an
extremely inefficient way to hold an array of 5 booleans. Your
std::valarray will be 16 bytes in size (judging from a quick gcc test),
with a pointer to a heap-allocated block for the actual data. The
obvious way to store 5 booleans is a single uint8_t with one bit per
item. This would be massively simpler and faster, reducing your
comparison to a single compare (rather than a loop) without any
indirection, and making your struct trivially copyable.
 
And if you really need such a big and complex structure, then have an
array of pointers to the structs, and sort the pointer array - that will
be much faster in C qsort or C++ std::sort.
Melzzzzz <Melzzzzz@zzzzz.com>: Nov 15 10:34PM

> https://sourceforge.net/p/sdcc/code/HEAD/tree/branches/lospre-vs-mcpre/sdcc/src/SDCClospre.hpp)
> are structs containing three members: An boost::tuple<float, float>, an
> std::valarray<bool> and a comparison function.
 
valarray probably allocates during swap.
 
 
--
current job title: senior software engineer
skills: c++,c,rust,go,nim,haskell...
 
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Nov 14 09:12PM -0800

On 11/14/2020 1:20 PM, Amine Moulay Ramdane wrote:
 
> The reference counter, which is incremented and decremented atomically, tracks the number of owning shared_ptr instances."
 
> So as you notice it has to atomically increment and decrement , so i don't think C++ reference counting is scalable.
 
> So I don't want to waste my time with C++ or Rust or other languages that have not a scalable reference counting.
 
Is yours similar to a split counter?
Bonita Montero <Bonita.Montero@gmail.com>: Nov 15 09:28AM +0100

> So as you notice it has to atomically increment and decrement , so i don't think C++ reference counting is scalable.
 
If it would be MT-safe, the reference-counters have to be atomic.
Nikki Locke <nikki@trumphurst.com>: Nov 14 11:23PM

Available C++ Libraries FAQ
 
URL: http://www.trumphurst.com/cpplibs/
 
This is a searchable list of libraries and utilities (both free
and commercial) available to C++ programmers.
 
If you know of a library which is not in the list, why not fill
in the form at http://www.trumphurst.com/cpplibs/cppsub.php
 
Maintainer: Nikki Locke - if you wish to contact me, please use the form on the website.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)