Is C++ superset of C?

14, Dec, 2018

Have you ever think that source which is valid C program and at the same time valid C++ code may behave differently?

int foo(float a) {
    auto v = a;
    return v > 0;
}

int main() {
    return foo(0.5f);
}

C– Lambda++

8, Dec, 2018

In the meantime, I am in lisp/scheme thing. The functional-like structuring manner, can be quite enlightening to day-to-day C tasks. Just simple closure passing in scheme:

(define foo (lambda (x) (lambda (y) (+ x y))))
(define bar (lambda (f i) (f i)))
(bar (foo 3) 5)

And then I got the “wonderful” idea. Lets try this in C++:

auto foo(int x) {
    return [x](int y) { return x+y; };
}

int bar(???? f, int i) {
    return f(i);
}

int main(int argc, const char * argv[]) {
    printf("%dn", bar(foo(5)), 3);
    return 0;
}

and when I simply wanted to pass lambda created by foo to function bar, I got a moment of WHAAAT!? Is the std::function the only option to pass lambda with captures (you cannot pass lambda with capture by cast to function pointer). This is ridiculous.

TinyScheme

2, Dec, 2018

The TinyScheme is really tiny. One evening to port it to the Amiga. One interesting thing - I needed to switch from malloc to calloc because of interpreter string comparison errors. Does all new systems clear the buffer returned from malloc? Have security won with performance?

List vs Array

25, Nov, 2018
I was searching about performance differences of array vs list. I have found only some very populistic measurements - like removal of random element in list with random access (using linear search each time). This is somehow unrealistic usage for that structure. My need would be to frequently iterate over elements, and when something happen during the inspection of the item it will be deleted. Something like per frame game update. So, to compare more realistic usages, I have made simple
implementation and tests.

I made two implementations of list - one with custom allocator, one with malloc. I wanted to test simple unordered insertion (so at the end), iteration and deletion time (at any place). For deletion I have made additional optimized version for array which first marks elements to be removed and then remove them in one batch. Also I have tested cache coherent order vs cache unfriendly memory arrangement for the list nodes. So here are results:

List with malloc/free; time spend in list compared to array:

OP/#    4K      64K     256K      Items count
ADD     14.8    14.4    14.4      Simple insertion at the end.
ITER    3.42    3.54    2.56      Simple iteration over the items.
DEL     0.13    0.0091  0.0011    Delete each 8th element.
DEL*    2.67    1.77    1.62      Defered delete - mark each 8th element and delete at once.

List with custom allocator; time spend in list compared to array:

OP/#    4K      64K     256K        Items count
ADD     1.97    1.98    2.28        Simple insertion at the end.
ITER    5.46    3.96    1.76        Simple iteration over the items.
ITER*   27.87   39.69   38.26       Cache missed iteration over the items.
DEL     0.017   0.0022  0.00028     Delete each 8th element.
DEL*    0.36    0.365   0.49        Defered delete - mark each 8th element and delete at once.
So, it can be surely seen that list is slower for all except deletion. However, arrays may be faster in deletion if you use std allocator. Call to free() is significant. Insertion with malloc was about 14x time slower than array insertion at the end. However, with custom allocator it is not a case, and other times are not so bigger than array implementation. Then lists rocks at deletion. The iteration and insertion times are higher roughly 2x - as the memory consumption also is 2x higher. But it is crucial for iteration over list is to maintain good cache coherency in the allocator (the penalty is 20x compared to cache friendly access).

Another tests would be needed in concurrent environment. Maybe I will do it in future. There list may win as locks may be local not global (or even lock free or persistent approaches may be used). Also, one may test insertion in the middle - but this clearly changes nothing for list and for array will drop performance to deletion case.

Bye bye github

23, Oct, 2018

Today, the last day on github. Why:
- slow fetches;
- increasingly unreliable, I am bored to check status.github.com;
- not so well support for git-lfs, with DLC like bandwith pricing plan;
- I consider an acquisition by MS as a security risk..

I am moving to hub.darcs.net…

Chasing Java

20, Oct, 2018

+7% for C -> https://www.tiobe.com/tiobe-index/

Traps of hashing floats

6, Oct, 2018

A common way to compare two floats is something like:

float_cmp(float a, float b) { 
    return fabsf(a-b) < eps; 
}

and the common way of hashing these is something like:

unsigned float_hsh(float a, unsigned sz) {
    return (unsigned)(a * p) % sz; 
}
where p is some big prime. But there is non-trivial problem with these formulations when used together. The float_hsh has non-constant window in which two distinct but very close floating numbers will generate the same hash value. It is not bad at itself (just a little non-uniformity in hashing). But look at float_cmp. It will return true for range of floats - not single floats. This may result in two equal numbers with differnt hashes (and yes, it will happen, if you do some non-trivial algorithms with these numbers with hardly predictable rounding issues). This is a violation of one of the hashing invariants (that the same numbers will have same hash index). You may think:
unsigned float_hsh(float a, unsigned sz) { 
    return (unsigned)(roundto(a, eps) * p) % sz; 
}
will solve this. But apparently also not entirely. This because float_cmp() measures epsilon in relative space (starting at a and going to b), but float_hsh() has error correction in absolute space (starting at origin - 0). So float equality also must be appended:
float_cmp(float a, float b) { 
    return roundto(a, eps) - roundto(b, eps); 
}
This also may have some issues with precision (as it converts floating point number to a fixed one). But, this is another story…

Tell me why?

2, Oct, 2018

Just trying to make portable file handling…

long int ftell ( FILE * stream ); /* Win64 - 32bit return */ 
long int ftell ( FILE * stream ); /* GNU/BSD - 64bit return*/

Why LLP64? Some systems are a series of interesting mistakes.

memfrob() __attribute__((rotfl))

29, Sep, 2018

Found accidentally:

void *memfrob(void *s, size_t n);

The memfrob() function encrypts the first n bytes of the memory area
s by exclusive-ORing each character with the number 42.

http://man7.org/linu … /man3/memfrob.3.html

Realloc inplace?

28, Sep, 2018

Sometimes it would be nice to have realloc which does not move (eg. graph with pointers backed in array). That’s easy. The trick is to reserve first the big chunk of address space and then allocate or deallocate memory in that particular address space.

On Unixes:
- reserve address space

mmap(NULL, max_length, PROT_NONE, MAP_PRIVATE | MAP_ANON, -1, 0); /* reserve */

- (re)alloc in grow direction

mprotect(addr, current_length, PROT_READ | PROT_WRITE);

- shrink/dealloc

madvise(addr + new_length, current_length - new_length, MADV_DONTNEED);

On Windows:
- reserve address space

VirtualAlloc(NULL, max_length, MEM_RESERVE, PAGE_NOACCESS);

- (re)alloc in grow direction

VirtualAlloc(addr, current_length, MEM_COMMIT, PAGE_READWRITE);

- shrink/dealloc

VirtualAlloc(addr + new_length, current_length - new_length, MEM_RESET, PAGE_NOACCESS);

Limitation: you have “only” 128TB of address space on amd64.

Are macros needed for generics in C?

24, Sep, 2018

Generic code in C mostly look like this:

#define MAP(BAR) {
    for (int i = 0; i < ...; ++i) {
        BAR(i);
    }
}

But with little work it may look like that:

static inline void map(void (*bar)(int)) {
    for (int i = 0; i < ...; ++i) {
        bar(i);
    }
}

But then question arises. If you call like this:

map(&foo);

will the compiler optimize foo and call it directly?

Yes (tested gcc and clang -O2). Even more - in my test, it inlined body of foo also…

The most unused C operator?

15, Sep, 2018

And the winner is - the unary plus.

+a

The integer promotion.

Capture syntax in C?

15, Sep, 2018

It has been there, since K&R:

foo() {
    extern int a;
    
    return a;
}

int a = 0;

C smart limitation?

13, Sep, 2018

In “old C” all local variables were declared at block beginning:

int foo(int n) {
    int i;
    int s = 0;

    for (i = 0; i < n; ++i) {
        s+=i;
    }

    return s;
}

Quite limiting to what we have today?! But this, quite surprisingly, made life safer in some situations. Consider this goto end pattern (which I saw used in production code)

int foo(int n) {
    ...
    if (some error) goto clean;
    ...
    void *ptr = create()
    ...
clean:
    if (ptr) release(ptr) /* Crash on some error.. */

    return s;
}

It looks like new features make some more dangerous (even when these were obscure from beginning).

Compile time assertion in C?

31, Aug, 2018
#define CASSERT(E) sizeof(char [(E) ? 1 : -1])

Accessors

18, May, 2018

Do all accsessors need to have costly bound checking like this:

T get(Array *a, unsigned int index) {
    assert(a);

    if (index < a->count) {
          return a->store[index];
    }

    return NOT_A_T;
}

If you can afford for only-power-of-twos array, the above code may be:

T get(Array *a, unsigned int index) {
    assert(a);
    assert(a->mask == a->count - 1);

    return a->store[index & a->mask];
}

If you go further and limit array size to powers of 256 you may:

T get(Array *a, unsigned char index) {
    assert(a);
    assert(0x100 == a->count);

    return a->store[index];
}

or

T get(Array *a, unsigned short index) {
    assert(a);
    assert(0x10000 == a->count);

    return a->store[index];
}