[prev in list] [next in list] [prev in thread] [next in thread] 

List:       hpux-cxx-dev
Subject:    Re: CXX-DEV: list::splice not constant time compexity
From:       Martin Sebor <sebor () roguewave ! com>
Date:       2005-04-08 20:04:56
Message-ID: 4256E3E8.2000000 () roguewave ! com
[Download RAW message or body]

Dennis Handly wrote:
>>From: Jack Marr <marr@ugs.com>
>>One of our developers is saying that the implementation of list:splice
>>bundled with aCC 3.52 doesn't achieve constant time complexity as
>>specified by the C++ standard (23.2.2.4/6).  I'm wondering if the issue
>>is solved in a later version of Rogue Wave (this version seems to be
>>2.2.1 => _RWSTD_VER is 0x02020100) and if that later version is bundled
>>with a more current version of aCC.
> 
> 
> This may have been discussed here before??
> 
> Basically Martin helped make a fix for JAGad87020.  This caused a memory
> corruption so we had to back it out.  And there is probably no way to
> implement this in a binary compatible way.

The fix we have implemented is not binary compatible.

> 
> I assume RW has a newer version that fixes the problem but it isn't
> bundled with aC++.

Yes. Unfortunately, it's not the default implementation (i.e.,
it has to be enabled by setting a macro). I'm not sure when/if
we'll change it. Apparently there are users who like the current
behavior (it makes other list modifications quite a bit faster).

> 
> We did leave in the "bad" code from JAGad87020 but you have to compile
> with -D_HP_FAST_LIST_SPLICE.
> 
> This is probably dangerous.  It means you can't ever destroy those
> lists, without first putting the elements back where you got them.

IIRC, this was the naive fix that preserved the memory management
code (i.e., the node buffers). The fix we have in place now gets
rid of these buffers and allocates each node separately. Another
solution would be to change splice to transfer whole buffers from
the spliced list (and copy the remaining nodes as is done now).
That would give us an amortized constant complexity on average.
I'm not sure it's worth the effort.

Martin
 _________________________________________________________________
 To leave this mailing list, send mail to majordomo@cxx.cup.hp.com
    with the message UNSUBSCRIBE cxx-dev
 _________________________________________________________________
[prev in list] [next in list] [prev in thread] [next in thread]