On 9/27/06, skaller <[EMAIL PROTECTED]> wrote:
The design in the STL, and the growth is exponential so that the
average cost of copies does not affect the average complexity
of adding an item (it's constant, and you can't do better than that,
you can only improve the constant).
But there's no way to get below constant-time per item for growth,
so you're just tweaking a trade-off between memory use and speed.
We can look at all possible memory map/memory layouts, and in a
small fraction (defined almost however you like) there will be space
available to extend without moving.
Certainly you can design a language in which this is true. It won't
interface so well to C++ if you make this so for all types though.
There's manifestly something amiss if you keep quoting
O(1) vs O(n), when the O(n) occurs 1 time in n, giving an
average cost that is O(1), assuming that exponential
growth is used. I repeat: when exponential growth is
viable, all else is just adjusting constant factors, and
they're not terrible constant factors in the first place (a
typical implementation copies a given object twice if
items are push_back'd into an empty vector, versus
just once if the vector was reserve'd to the right size).
There is a miscommunication here: changing the allocator interface
allows for realloc-like semantics. mmap games are another matter
entirely, and do need the more radical surgery to the object model
that you appear to be advocating.
Not very relevant: the cost of each such operation is linear anyway,
and again the difference is a constant factor (typically around 2).
Such a viewpoint will alienate your intended user base, and it's
far from true. Maybe if you say something concrete, it can be
concretely refuted.
A domain with which I'm very familiar. And indeed I've worked
around a performance problem on Solaris, by avoiding use
of Rogue Wave's terrible almost-implementation of std::string.
(Copying wasn't the problem; doing almost anything to a string
on that platform is pathetically slow because of an attempt to
do multi-thread safe copy-on-write for std::string, and the
absence of any small-string optimization.)
strftime was also astonishingly slow on Solaris 8; it's orders of
(decimal) magnitude faster on recent versions.
[snip]
The std::string implementation on Solaris is the most inefficient
I have ever encountered, by orders of magnitude, and I've also
expended significant effort in working around it. In no way does
it reflect on issues in resizing vectors, which (as noted here, in
more detail than before) should give no more than a factor of 2
slowdown and even that only on code inserting into a vector
without using reserve.
-- James
On Tue, 2006-09-26 at 21:39 -0700, James Dennett wrote:
> skaller wrote:
> > Suppose you have a large vector and want to extend it,
> > say with 'push_back'.
> >
> >
> (Which, by design, happens only rarely, because of the exponential
> growth.)
By whose design, and why is the growth exponential?
The design in the STL, and the growth is exponential so that the
average cost of copies does not affect the average complexity
of adding an item (it's constant, and you can't do better than that,
you can only improve the constant).
I have a published work .. with benchmarks .. on this subject.
It happened to be in the context of arrays used for
bignum arithmetic. My implementation accepted a user defined
function which computed the desired size of the array.
With that implementation, the growth is whatever you want.
But there's no way to get below constant-time per item for growth,
so you're just tweaking a trade-off between memory use and speed.
> There are a small number of cases in which this helps significantly;
> it depends on having either spare memory at the right address, or
> spare address space.
I'm not sure what you mean by 'small number of cases'.
We can look at all possible memory map/memory layouts, and in a
small fraction (defined almost however you like) there will be space
available to extend without moving.
> (Or, less pleasant, you can change the addresses,
> which _is_ a move, but a particularly violent form of move.)
It's related to a move, yes. But then, copy, default init,
copy assign, move, remap, destroy are all what I'd call
"generic" operations that apply to all first class types.
Certainly you can design a language in which this is true. It won't
interface so well to C++ if you make this so for all types though.
> I'd be interested to see how that benchmarks for various uses.
Me too .. but clearly there is manifestly a difference
between O(1) and O(n) complexity .. on the assumption the
underlying kernel call is fast .. of course the kernel
operation requires remapping pages by adjusting page
tables, proportional to the array length, so it depends
partly on how the kernel page tables are managed.
In principle the kernel operation is probably linear too.
There's manifestly something amiss if you keep quoting
O(1) vs O(n), when the O(n) occurs 1 time in n, giving an
average cost that is O(1), assuming that exponential
growth is used. I repeat: when exponential growth is
viable, all else is just adjusting constant factors, and
they're not terrible constant factors in the first place (a
typical implementation copies a given object twice if
items are push_back'd into an empty vector, versus
just once if the vector was reserve'd to the right size).
> In as much as it's true, this is a limitation of C++98's allocator
> interface, and numerous proposals have been sketched to allow
> object-aware realloc equivalents.
That may be partly true, but only partly. Being able to move
and/or remap an object in C++ requires user written code
like a copy constructor .. and the lack of an appropriate
'method' is a restriction of the fundamental class structure:
that is, it isn't just a problem with a library routine like
the allocator interface .. its a fundamental problem of
C++ object semantics.
There is a miscommunication here: changing the allocator interface
allows for realloc-like semantics. mmap games are another matter
entirely, and do need the more radical surgery to the object model
that you appear to be advocating.
> Also note: this is linear time, but it happens with frequency inversely
> proportional to the array length, hence is "amortized constant".
That is only true for a linearly growing array. If you consider
an exponential operation:
x += x
and doubling of storage, then the copy is done *every* operation,
whereas for mmap it is never done.
Not very relevant: the cost of each such operation is linear anyway,
and again the difference is a constant factor (typically around 2).
One also has to consider random lengths, shrinkage, etc.
> > But this is NOT what is required for mmap.
> > What you want is an 'in place after the fact adjustment'
> > or an 'in place before the fact adjustment'.
> That's one way to handle things.
If there's another way I'd sure like to hear about it!
As it is, it requires MMAP_ANONYMOUS to do it easily and
that is only available on Linux.
> It's true that the C++ object model doesn't sit well with collectors
> that like to move objects.
When I started working on Felix I wasn't really aware of this
kind of issue. The current Felix collector allows marking
some types 'immobile' which prevents them being moved.
Probably this should be the default for opaque C++ types ..
but it isn't, because most of them CAN be moved with
memcpy. Luckily the default collector doesn't move things :)
> I don't think there's any way to interface to C++ code which would
> allow you to change the addresses of its objects.
For a simple type, surely there is: the user just specifies
the move routine. For example something like:
type tree = "tree" with move="tree_move";
If you leave out the move method, memcpy is used.
If the object can't be moved then:
immobile type tree = "tree";
> On the bright side, extensive measurements don't seem to show that
> there are common situations where this makes much of an improvement
> anyway --
Extensive measurements by C++ programmers on typical C++ code
are basically worthless.
Such a viewpoint will alienate your intended user base, and it's
far from true. Maybe if you say something concrete, it can be
concretely refuted.
> time spent in copying/resizing vectors is usually trivial, and
> becomes even more so with move semantics. The additional gain from
> playing memory map games, in applications I've seen, would be
> essentially negligible.
My experience is different. The actual environment for which
Felix was designed was a telco. In this environment the system
had to handle a certain number of phone calls, and a certain
rate of new phone calls.
The system was 1 decimal order of magnitude too slow,
and profiling and other analysis revealed that almost the whole
of the problem could be attributed to C++ string copy semantics.
(Data had to be moved across a lot of abstraction layers typical
in a networking protocol stack)
A domain with which I'm very familiar. And indeed I've worked
around a performance problem on Solaris, by avoiding use
of Rogue Wave's terrible almost-implementation of std::string.
(Copying wasn't the problem; doing almost anything to a string
on that platform is pathetically slow because of an attempt to
do multi-thread safe copy-on-write for std::string, and the
absence of any small-string optimization.)
strftime was also astonishingly slow on Solaris 8; it's orders of
(decimal) magnitude faster on recent versions.
Quite a bit of works was done with what one developer called
'vampiric clones' which is essentially a move
[snip]
The point is your 'essentially negligible' is my
'essential makes the application impossible to implement'.
The std::string implementation on Solaris is the most inefficient
I have ever encountered, by orders of magnitude, and I've also
expended significant effort in working around it. In no way does
it reflect on issues in resizing vectors, which (as noted here, in
more detail than before) should give no more than a factor of 2
slowdown and even that only on code inserting into a vector
without using reserve.
-- James
------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys -- and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________ Felix-language mailing list Felix-language@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/felix-language
