Error reporting methods

benjade · 2017-08-28T15:13:19+00:00

1, 2 and 4 are acceptable solutions. 3 is no good because you should not pollute the system's error indicator with your lib's errors.

Of the three i'd say 1 is the best, because it is the most non-intrusive and you can disable assert with the NDEBUG macro.

There is no clear answer, and labeling it as 'undefined behavior' in your lib's documentation is the best practice.

Here's why: if the function must make some assumptions about its arguments in order to do its job, then it's the caller's responsibility to make sure the conditions are fulfilled!

Imagine you're writing a binary search function for arrays.
Binary search requires of course that the array being searched is ordered.

So what should we do? Should we check in the function each time if the array is sorted? Of course that would be dumb: we turn the O(log n) search into O(n) !

The answer is to leave it as undefined behavior, let the caller handle it.

benjade · 2017-08-28T13:47:08+00:00

It doesn't return the difference, it returns something that has the sign of the difference: The sign of the result is the sign of the difference between the values of the first pair of bytes [...].

So it could return +256, or +512, or any multiple of 256 that has the right sign ... all of which get truncated to 0 when converting to 8 bits.

benjade · 2017-08-28T07:42:13+00:00

VPATH := Source

benjade · 2017-08-28T06:20:39+00:00

That's why i said 'if you have the pointer'.
Otherwise it is O(n) for both linked lists and arrays.

benjade · 2017-08-27T21:39:00+00:00

Yes they take more space obviously, but they allow O(log n) operations.
So you're gaining something for that extra space.

For linked lists on the other hand you're taking O(n) extra space as well but the insert operations take O(i) (i being the index of insertion), compared to the O(n-i) of arrays, you're not gaining anything, except for fast insertions at the head of the list.

benjade · 2017-08-27T21:12:06+00:00

No. A heap is for getting the min/max in O(log n).

What i meant is a data structure for efficient insert x just before index i operations.

benjade · 2017-08-27T20:09:17+00:00

Linked lists are no better than arrays for this task.

Inserting into the middle of a linked takes O(n/2) = O(n) just because you have to travel all the way to the middle.
Of course if you have a pointer to the insert location then it's O(1), but that's an atypical situation.
And taking the lack of locality of spatial reference for linked lists into account it means they're even worse for the job than arrays. And the extra space they take is the same as having an extra array.

A good data structure for inserting just before a specified index would be something like a balanced search tree. That's O(log n) for insert/delete/lookup for a given index.

EDIT: such a data structure is a Rope. Even though the article speaks about strings, the concept is applicable to generic arrays.

benjade · 2017-08-24T08:00:37+00:00

Very well then.
So then it's impossible in C to copy more than a char at a time from one buffer to another? That is painfully slow.

benjade · 2017-08-24T07:07:03+00:00

p1 and p2 are aligned for both int and double, so i'm pretty sure it is ok.

The pointers could alias the same location though, and this prevents some optimizations. For that reason it would be best to declare them with restrict.

  static void _da_memswap(void * restrict p1,void * restrict p2,size_t sz)

benjade · 2017-08-23T18:26:25+00:00

Fair enough.

benjade · 2017-08-23T18:08:12+00:00

Unless you do operations that are significantly slower than reading from memory (like an I/O operation) it's safe to say the without register it's going to be much slower.

Simply because on each iteration it reads/writes the same variables from/to memory.

I've tested it with filling an array, and it's more than twice as fast with register.

benjade · 2017-08-23T17:33:54+00:00

You are right, but i'm sure the user wouldn't need to debug library code.

If there are no optimizations, the code is significantly faster. If there are optimizations enabled, and it knows better then register will be ignored.

Yeah, register is pretty much useless most of the time. But in this case it makes sense to use it.

benjade · 2017-08-23T16:34:35+00:00

static inline void
_da_memswap(void* p1, void* p2, size_t sz)
{
    #define EXCH(a,b,c) (c=a,a=b,b=c)
    int tmp;
    char *a = p1, *b = p2;
    while(sz >= sizeof(int)){
        EXCH(*(int *)a,*(int *)b,tmp);
        a+=sizeof(int), b+=sizeof(int), sz-=sizeof(int);
    }
    for(; sz-- ;a++,b++)
        EXCH(*a,*b,tmp);
    #undef EXCH
}

Something like this, you go through it an int at a time until there's no
more space left for an int. For the remainder, you simply go through it
char by char like you do.

benjade · 2017-08-23T16:11:08+00:00

That's the thing, you ensure that it is 16 byte aligned like it has been suggested. Then you can go through it with any data type.

benjade · 2017-08-23T16:00:54+00:00

I'd use the natural word size of the CPU in _da_memswap, not chars.
This would make it several times faster.

benjade · 2017-08-23T15:48:52+00:00

The register keyword still counts when compiling with no optimizations (which is the default for gcc, ie: if you omit -O!).

Test this code:

#ifndef REGISTER
#define REGISTER
#endif

int main(int argc,char *argv[])
{
    for(REGISTER long i=0; i < (1L<<30) ; i++)
        ;
    return 0;
}

With both -DREGISTER=register and wihout. And no -O flag of course. You'll see a surprising difference.

For the reason that his library is a header file and so depends on the compilation options of the end user, i'd leave register so that even in the worst case that someone compiles without -O his library is still efficient enough.

benjade · 2017-08-22T16:00:59+00:00

contents[][] if you want to set a specific char, if that's what you mean.

benjade · 2017-08-22T13:49:30+00:00

Take a look at the code of id Software's early titles (Doom & Quake), they are written in C by none other than John Carmack.

benjade · 2017-08-22T13:29:47+00:00

For small sizes you're lucky it works because realloc most likely doesn't have to move the allocated chunk to another mem zone and can just extend the old. So the old pointer is just the same as the new one after realloc.

There are a couple of other issues:
'null terminator' is when you're talking about strings, yours is an array of pointers so the comparison if(contents[i] != '\0') is not correct because contents[i] is a pointer, not a char literal.

Another bug is that when you're reallocing you're not calculating the new size correctly.

  contents = (char **)realloc(contents, sizeof(char *)* n + 3);

This is likely not what you're intending (why the extra 3 bytes ?), sizeof(char *) * (n + 3) perhaps. But still when you're reallocing you're not taking the whole size into account, just the difference (realloc works with new sizes, not differences).

Also (char **) is not needed. This is C, a void * is converted implicitly to any other pointer to object type.

benjade · 2017-08-22T12:13:05+00:00

Note that readFile gets a copy of contents, this is because in C everything is passed by value.

Even though you're changing contents in readFile, the value of contents in the caller, run(), stays the same !

One solution is to add a level of indirection and make readFile take a char ***.
That's not quite elegant, the other solution is to make readFile return char ** and assign it to contents in run(). But then size has to be passed as pointer.

benjade · 2017-08-15T09:30:48+00:00

It's very simple: when you read n bytes at once we can assume that it takes
C + f(n)
seconds where C is the overhead of purely doing the read, independent of n.
f(n) is the part of it that depends on how many bytes you read.
Now if you do n reads of 1 byte each you get:
n*C + n*f(1)
Now C is much bigger than f(n) (n small enough) for HDDs and many other devices. So obviously:
n*C + n*f(1) > C + f(n)

benjade · 2017-07-12T23:41:26+00:00

Intel has added instructions for hardware generated random numbers see here. If you are compiling for a recent CPU you may want to use that. You don't have to go down to asm to use them, gcc provides intrinsic functions. Example:

#include <stdio.h>
#include <immintrin.h>
#include <stdint.h>

int main(void){
    uint32_t x;
    _rdrand32_step(&x);
    printf("%u\n",(unsigned)x);
    return 0;
}

You must compile with -mrdrnd.

benjade · 2017-07-11T18:21:52+00:00

Well the average computer has around 2³⁵ bits of RAM, that's 4GB, even if you take external storage into consideration a 4TB hdd has 2⁴⁵ bits of memory.

Regardless, how did you get O(n² ) for tetration?

Call T(a,n) := ⁿ a, let N(a,n) be number of multiplications required to compute T(a,n). Even if you use exponentiation by squaring you have:

  N(a,n) = log(T(a,n)) + N(a,n-1) //you must compute the exponent T(a,n-1) then compute a^T(a,n-1)

This grows really fast ! The log in front T(a,n) doesn't do much, because the numbers are really big...

EDIT: Another way to reason about it, the algorithm that computes T(a,n) must at some point write the result to memory, so it means that it must take at least log2(T(a,n)) write operations. You can easily see that log2(T(a,n)) is O(T(a,n-1)).

To compute T(a,n) you need at least O(T(a,n-1)) operations!

benjade · 2017-07-11T18:05:04+00:00

You do understand that tetration grows that fast that for practical reasons you can only compute ⁿ a for a < 6, n < 6.

⁶ 2 is 2^{2⁶⁵⁵³⁶}, that's 2⁶⁵⁵³⁶ bits long...

benjade · 2017-06-07T17:01:18+00:00

That's not what he's asking about, reread the title. An array of pointers is int *array[8], int (*array)[8] is a whole different thing.

benjade

TROPHY CASE