Re: C++ in embedded systems

From: CBFalconer (cbfalconer_at_yahoo.com)
Date: 08/16/03 

Date: Sat, 16 Aug 2003 15:24:08 GMT

Jyrki O Saarinen wrote:
> In comp.arch.embedded CBFalconer <cbfalconer@yahoo.com> wrote:
>
> <about hashlib module>
> : However there are the equivalent of constructors and destructors,
> : both for complete hash tables and for items to be stored, and
> : operations to be performed on them. But there is no C++ bloat (it
> : is written in C) and no known re-entrancy problems.
>
> What C++ bloat?
>
> An implementation with the same features done with
> C++ is likely to be smaller and faster than a C implementation,
> because 'void *' is not used which causes aliasing problem and prevents
> some optimizations. C99 has the 'restrict' keyword these days though..:
> http://www.lysator.liu.se/c/restrict.html
>
> Also inlining hashing and especially equality comparasion code in C++
> implementation likely increases performance and even might reduce size.
> We'll see what happens..
>
> I'm in the process of writing an implementation using interfaces and
> inheritance for hash- and equality comparaision function pointers
> instead. Comparing C implementation template-based implementation
> isn't probably fair, but that would make even more difference.
>
> The difference between C++ and C implementation isn't going to be very
> high with a reasoable hash function since it probably dominates,
> but I guess the difference could be tested by a hash function that runs
> in a short constant time. Although in C++ implementation returning 0 as
> a hash value results in the compiler probably detecting it and
> elimination of few statements, so that's not a very good comparasion
> either.. I'll try to figure something out.

The hash function is external in hashlib. It belongs to the data
itself, since what is a good function depends on the data makeup.
Similarly the equivalent of constructors and destructors for the
items to be stored. The provided string hashing functions are
purely for convenience, because strings are probably the most
prevalent data keys.

>
> I'll compile your code and my code using gcc 3.3.1 cross compilers for
> AVR and H8. Any preference which models?
>
> This will probably take few days since it has been a while I have been
> programming C++, and I have to make myself more familiar with your test
> code of hashlib.c so that I can verify my implementation.

It should all compile out of the box. Supposedly it is in pure
portable standard C. The tests depend on the Mersenne Twister
(for portable repeatability) which in turn is not guaranteed
without a 32 bit unsigned long. hashlib.h has a __cplusplus
guard, so it should link to a C++ system immediately.

"splint -weak hashlib.c" generates no warnings. I consider the
warnings without -weak spurious, but they might be significant for
anyone modifying the code.

Under this system the hashlib module is less than 0x700 bytes of
code. 

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

Relevant Pages

  • Re: Some comments on "super fast hash"
    ... SFH seems reasonably good and certainly is fast. ... > a hash, and SFH does not. ... The latest versions of each hash function which leverages this ... it must behave worse on other key sets. ...
    (comp.programming)
  • Some comments on "super fast hash"
    ... I've implemented a hash function here: ... SFH seems reasonably good and certainly is fast. ... quality of the hash function is not affected by the difference as far ... it must behave worse on other key sets. ...
    (comp.programming)
  • Re: Maximum String size in Java?
    ... >> compilation on any new target platform that does not already have ... Do you have a version of SFH posted with changes to use this file ... If they intend to use a hash ... benefit of 31/33 will sway me into using more than one hash function. ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... chain style and reprobe style are basically a wash. ... will be a smaller chance of encountering deleted entries before it. ... Once you sufficiently optimize a hash table, ... by computing of the hash function). ...
    (comp.programming)
  • Re: Maximum String size in Java?
    ... The hash function will *NOT* have the minimal collision ... > for long strings, so on average, SFH bakes it in the performance ...
    (comp.programming)