• Scott Michel <scottm aero.org> Aug 17 2004
• "Walter" <newshound digitalmars.com> Aug 17 2004
• Scott Michel <scottm aero.org> Aug 18 2004
• "Walter" <newshound digitalmars.com> Aug 18 2004
• Scott Michel <scottm aero.org> Aug 18 2004
• "Walter" <newshound digitalmars.com> Aug 19 2004
• Scott Michel <scottm aero.org> Aug 18 2004
• "Walter" <newshound digitalmars.com> Aug 19 2004
• Scott Michel <scottm aero.org> Aug 19 2004
• Anuj Goyal <Anuj_member pathlink.com> Aug 21 2004
• Scott Michel <scottm aero.org> Aug 23 2004

Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

Walter:

Here is a "working" version of the maptest.cpp file from the previous 
message. It would have helped if I put the proper "-D" definitions on 
the command line. I've been staring at the STLport heap of steaming code 
for far too long.

I think I've encountered a legit compiler bug. If the enclosed 
maptest.cpp file is compiled with:

dmc -Ae -Ar -DSTRICT -D_CONSOLE=1 -D_STLP_USE_STATIC_LIB -D_DEBUG
	 -D_STLP_DEBUG -c maptest.cpp

The compiler will complain with:

maptest.cpp(24383) : Error: access declaration of base member 
'EH_allocator<TestClass >::_Non_const_traits' has storage class or type

If you look at the enclosed file, at or about line 25590, the multimap 
class attempts to instantiate the red-black tree. If you run the 
compiler with "-v", the _ConstIteTraits parameter to the 
_stlpdebug_Rb_tree template is EH_allocator<TestClass>. The 
_ConstIteTraits parameter should be _Const_traits<TestClass>, the _Alloc 
parameter should be EH_allocator<TestClass>. Looks like the compiler 
substituted the wrong parameter and missed substituting one.

I haven't been able to pare this one down to a two-line snippet.


-scooter

"Scott Michel" <scottm aero.org> wrote in message
news:cfudci$1n85$1 digitaldaemon.com...
 Walter:

 Here is a "working" version of the maptest.cpp file from the previous
 message. It would have helped if I put the proper "-D" definitions on
 the command line. I've been staring at the STLport heap of steaming code
 for far too long.

 I think I've encountered a legit compiler bug. If the enclosed
 maptest.cpp file is compiled with:

 dmc -Ae -Ar -DSTRICT -D_CONSOLE=1 -D_STLP_USE_STATIC_LIB -D_DEBUG
 -D_STLP_DEBUG -c maptest.cpp

 The compiler will complain with:

 maptest.cpp(24383) : Error: access declaration of base member
 'EH_allocator<TestClass >::_Non_const_traits' has storage class or type

 If you look at the enclosed file, at or about line 25590, the multimap
 class attempts to instantiate the red-black tree. If you run the
 compiler with "-v", the _ConstIteTraits parameter to the
 _stlpdebug_Rb_tree template is EH_allocator<TestClass>. The
 _ConstIteTraits parameter should be _Const_traits<TestClass>, the _Alloc
 parameter should be EH_allocator<TestClass>. Looks like the compiler
 substituted the wrong parameter and missed substituting one.

 I haven't been able to pare this one down to a two-line snippet.


Surely it can be pared down to less than 25,000 lines! (and please, email me
such gigantic files rather than posting them)

Walter wrote:
 Surely it can be pared down to less than 25,000 lines! (and please, email me
 such gigantic files rather than posting them)


I'm sure I can do something to make the problem more tractable. (and I 
didn't want to clog up your mailbox; in theory, I could put a link to my 
cs.ucla.edu web server instead.)


-scooter

"Scott Michel" <scottm aero.org> wrote in message
news:cg0dhc$vhj$1 digitaldaemon.com...
 Walter wrote:
 Surely it can be pared down to less than 25,000 lines! (and please,




 such gigantic files rather than posting them)


 I'm sure I can do something to make the problem more tractable. (and I
 didn't want to clog up your mailbox; in theory, I could put a link to my
 cs.ucla.edu web server instead.)


Not to worry, I have lots of local space. But very large files make the
newsgroup difficult to access for people with dialups. For posting
significant amounts of code of public interest, a link to a web site for
download is best.

Sorry to get you spun up -- I tracked down the problem to a typo in one 
of STLport's debug files. The clue was the misplaced parameter.

Should trust that the compiler is sturdy and code isn't. STLport seems 
to have pretty dodgy quality.


-scooter

"Scott Michel" <scottm aero.org> wrote in message
news:cg0p0b$1qb1$1 digitaldaemon.com...
 Sorry to get you spun up -- I tracked down the problem to a typo in one
 of STLport's debug files. The clue was the misplaced parameter.


Ah, I'm glad it was an easy problem to fix.

 Should trust that the compiler is sturdy and code isn't. STLport seems
 to have pretty dodgy quality.


No prob.

Onwards and upwards: I've gotten the exception handling program to 
compile but not link -- if I leave out the /co debugging info, the 
program links (but doesn't work). If I put in the /co debugging info, 
then OPTLINK craps out while writing the CV section. I used the 
/information switch to see what OPTLINK was doing.

Any ideas for debugging the problem?

"Scott Michel" <scottm aero.org> wrote in message
news:cg121f$2dhb$1 digitaldaemon.com...
 Onwards and upwards: I've gotten the exception handling program to
 compile but not link -- if I leave out the /co debugging info, the
 program links (but doesn't work). If I put in the /co debugging info,
 then OPTLINK craps out while writing the CV section. I used the
 /information switch to see what OPTLINK was doing.

 Any ideas for debugging the problem?


The compiler could be goofing up the CV data. One way to track this down is
to mix and match object files with CV on and off, if the CV problem can be
traced to one particular obj file.

Walter wrote:
 The compiler could be goofing up the CV data. One way to track this down is
 to mix and match object files with CV on and off, if the CV problem can be
 traced to one particular obj file.


<grunt><grumble>

The reference counting section in STLport is not consistent (see _thread.c or
_thread.c [can't remember the name] in the STLport/stlport/stl directory) ...
atomic increment is supported on some platforms (win32, solaris) but not others
(aix, linux).  If someone is interested, Alexander Terekhov has a good
discussion of proper reference counting.  He has posted a class that is
available on the Intel board.  C++ developers that deal with multiple platforms
may find it useful. (PS: how much do we have to pay walter to port DMC to the
linux platform, I bet it would beat the pants off of gcc).  D is a much better
language, but developers still have years of C++ that need support =)


http://softwareforums.intel.com/ids/board/message?board.id=42&message.id=243

/* This is Alexanders' experimental C++ take on >UNOFFICIAL<
"pthread_refcount_t"-API
----------------------------------------------------------------------------

File: refcount.cpp

Originally written by Alexander Terekhov and released into the public domain.
This may be used for any purposes whatsoever without acknowledgment. Thanks 
for the assistance and support of Pavel Vasiliev, Mike Mowbray, c.p.t.-group
participants and everyone contributing, testing, and using this code.

http://groups.google.com/groups?threadm=3E4820EE.6F408B25%40web.de
(Subject: Re: threadsafe reference counting)

----------------------------------------------------------------------------
*/

#include 
#include 
#include 

struct msync { 
enum hlb_t   { hlb   }; // hoist-load barrier
enum ddhlb_t { ddhlb }; // hoist-load barrier with data-dependency "hint"
enum hsb_t   { hsb   }; // hoist-store barrier
enum slb_t   { slb   }; // sink-load barrier
enum ddslb_t { ddslb }; // sink-load barrier with data-dependency "hint"
enum ssb_t   { ssb   }; // sink-store barrier
enum acq_t   { acq   }; // hoist-load + hoist-store barrier
enum rel_t   { rel   }; // sink-load + sink-store barrier
enum none_t  { none  }; // naked
};

template
struct atomic { // 
atomic(T n) : t(n) { }
T load(msync::none_t) const { return t;}
T load(msync::hlb_t) const { return t; }
T load(msync::ddhlb_t) const { return t; }
void store(T n, msync::none_t) { t = n; }
void store(T n, msync::ssb_t) { t = n; }
void store(T n, msync::acq_t) { t = n; }
void store(T n, msync::rel_t) { t = n; }
bool attempt_update(T o,T n, msync::none_t) { return (t == o) ? (t=n, true) :
false; }
bool attempt_update(T o,T n, msync::ssb_t) { return (t == o) ? (t=n, true) :
false; }
bool attempt_update(T o,T n, msync::acq_t) { return (t == o) ? (t=n, true) :
false; }
bool attempt_update(T o,T n, msync::rel_t) { return (t == o) ? (t=n, true) :
false; }
T t;
};

enum thread_safety { unsafe, basic }; // strong aside for a moment

template
class refcount;

template
class is_nonnegative; // just to suppress gcc 3.2 warning

template<>
struct is_nonnegative {
template
static bool test(numeric) { return true; } 
};

template<>
struct is_nonnegative {
template
static bool test(numeric value) { return value >= 0; } 
};

template
class refcount {

numeric m_value;

public:

static numeric min() throw() {
return std::numeric_limits::min();
}

static numeric max() throw() {
return std::numeric_limits::max();
}

refcount(numeric initial_value = min()) throw() :
m_value(initial_value) {
}

numeric get() const throw() {
return m_value;
}

void set(numeric value) throw() {
m_value = value;
}

void increment() throw() {
assert(max() > m_value);
++m_value;
}

void add(numeric value) throw(std::overflow_error) {
assert(is_nonnegative::is_signed>::test(value));
if (max() - value < m_value) 
throw std::overflow_error("refcount::add(): overflow");
m_value += value;
}

bool increment_if_not_min() throw() {
assert(max() > m_value);
if (min() == m_value) 
return false;
++m_value;
return true;
}

bool add_if_not_min(numeric value) throw(std::overflow_error) {
assert(is_nonnegative::is_signed>::test(value));
if (max() - value < m_value) 
throw std::overflow_error("refcount::add_if_not_min(): overflow");
if (min() == m_value) 
return false;
m_value += value;
return true;
}

bool decrement() throw() {
assert(min() < m_value);
return min() < --m_value;
}

bool decrement(msync::acq_t) throw() {
return decrement();
}

bool decrement(msync::rel_t) throw() {
return decrement();
}

bool decrement(msync::none_t) throw() {
return decrement();
}

bool subtract(numeric value) throw(std::underflow_error) {
assert(is_nonnegative::is_signed>::test(value));
if (min() + value > m_value) 
throw std::underflow_error("refcount::subtract(): underflow");
return min() < (m_value -= value);
}

bool subtract(numeric value, msync::acq_t) throw(std::underflow_error) {
return subtract(value);
}

bool subtract(numeric value, msync::rel_t) throw(std::underflow_error) {
return subtract(value);
}

bool subtract(numeric value, msync::none_t) throw(std::underflow_error) {
return subtract(value);
}

};

template
class refcount {

atomic m_value;

template
bool decrement(min_store_msync msm, attempt_update_msync aum) throw() {
numeric val;
do { 
val = m_value.load(msync::none);
assert(min() < val);
if (min() + 1 == val) {
m_value.store(min(), msm);
return false;
}
} while (!m_value.attempt_update(val, val - 1, aum));
return true;
}

template
bool subtract(numeric value, min_store_msync msm, attempt_update_msync aum) 
throw(std::underflow_error) {
assert(is_nonnegative::is_signed>::test(value));
numeric val;
do { 
val = m_value.load(msync::none);
if (min() + value > val) 
throw std::underflow_error("refcount::subtract(): underflow");
if (min() + value == val) {
m_value.store(min(), msm);
return false;
}
} while (!m_value.attempt_update(val, val - value, aum));
return true;
}

public:

static numeric min() throw() {
return std::numeric_limits::min();
}

static numeric max() throw() {
return std::numeric_limits::max();
}

refcount(numeric initial_value = min()) throw() :
m_value(initial_value) {
}

numeric get() const throw() {
return m_value.load(msync::none); 
}

void set(numeric value) throw() {
m_value.store(value, msync::none); 
}

void increment() throw() {
numeric val;
do { 
val = m_value.load(msync::none);
assert(max() > val);
} while (!m_value.attempt_update(val, val + 1, msync::none));
}

void add(numeric value) throw(std::overflow_error) {
assert(is_nonnegative::is_signed>::test(value));
numeric val; 
do { 
val = m_value.load(msync::none); 
if (max() - value < val)
throw std::overflow_error("refcount::add(): overflow");
} while (!m_value.attempt_update(val, val + value, msync::none));
}

bool increment_if_not_min() throw() {
numeric val;
do { 
val = m_value.load(msync::none); 
assert(max() > val);
if (min() == val)
return false;
} while (!m_value.attempt_update(val, val + 1, msync::none));
return true;
}

bool add_if_not_min(numeric value) throw(std::overflow_error) {
assert(is_nonnegative::is_signed>::test(value));
numeric val;
do { 
val = m_value.load(msync::none); 
if (max() - value < val)
throw std::overflow_error("refcount::add(): overflow");
if (min() == val)
return false;
} while (!m_value.attempt_update(val, val + value, msync::none));
return true;
}

bool decrement() throw() {
return decrement(msync::acq, msync::rel);
}

bool decrement(msync::acq_t) throw() {
return decrement(msync::acq, msync::none);
}

bool decrement(msync::rel_t) throw() {
return decrement(msync::none, msync::rel);
}

bool decrement(msync::none_t) throw() {
return decrement(msync::none, msync::none);
}

bool subtract(numeric value) throw(std::underflow_error) {
return subtract(value, msync::acq, msync::rel);
}

bool subtract(numeric value, msync::acq_t) throw(std::underflow_error) {
return subtract(value, msync::acq, msync::none);
}

bool subtract(numeric value, msync::rel_t) throw(std::underflow_error) {
return subtract(value, msync::none, msync::rel);
}

bool subtract(numeric value, msync::none_t) throw(std::underflow_error) {
return subtract(value, msync::none, msync::none);
}

};

Anuj Goyal wrote:

 The reference counting section in STLport is not consistent (see _thread.c or
 _thread.c [can't remember the name] in the STLport/stlport/stl directory) ...
 atomic increment is supported on some platforms (win32, solaris) but not others
 (aix, linux).  If someone is interested, Alexander Terekhov has a good
 discussion of proper reference counting.  He has posted a class that is
 available on the Intel board.  C++ developers that deal with multiple platforms
 may find it useful. (PS: how much do we have to pay walter to port DMC to the
 linux platform, I bet it would beat the pants off of gcc).  D is a much better
 language, but developers still have years of C++ that need support =)
 
 
 http://softwareforums.intel.com/ids/board/message?board.id=42&message.id=243


As interesting as that code is, it's incomplete. Technically accurate, 
in terms of what kinds of memory ordering primitives should, in theory, 
exist on a machine. But how many architectures have such fine-grained 
control over memory barriers? On Intel, you're lucky to have memory 
fences at all. The code is good for understanding all of the various 
issues faced by the developer in providing atomic operations, but seems 
to be somewhat impractical if not augmented by the appropriate amount of 
inline assembly.

Personally, I tend to prefer LL/SC semantics. This is achieveable on 
Intel using CMPXCHG -- see Jayanti, Petrovic, "Efficient and Practical 
Constructions of LL/SC Variables", PODC'03 (ACM). There's some overhead 
associated with doing LL/SC properly, namely the tags that have to go 
along with the shared variables, but that's not a bad price to pay for 
lock-free performance.