Re: Reducing unncessary string copying

[Joakim Sindholt <opensource zhasha com>]

On Mon, 2012-02-20 at 15:38 +0100, Enrico Weigelt wrote:
> * André Gillibert <metaentropy gmail com> schrieb:
> 
> > This adds some level of indirection to access the data bytes, and some
> > space overhead.
> > For example, the string "hello" is 6 bytes long (including the zero
> > terminator), with GLIBC's malloc, it may occupy 8 bytes (or maybe 16
> > bytes).
> > With your implementation, it would occupy twice as much memory.
> 
> No. With my approach, strings aren't a single bit longer.
> References to them require one more byte. (well, maybe more due padding).
> On certain platforms/architectures (eg. 64bit), we maybe even could put
> that single bit directly into the pointer (using the MSB if we can be
> sure the upper half is never used).
> 
> > Moreover, the binary code using strings would be larger of a few bytes too.
> 
> No. Plain access is not is not a single bit larger, ist just an offset.
> 
> My string reference looks like this:
> 
> typedef struct
> {
>     gchar* str;
>     unsigned char flags;
> }
> 
> > And so, once g_strdup() has been called, a new dynamic string is
> > created. Consequently, very few strings would be static.
> 
> g_strdup() wont be called (directly) very often.
> Code that is operating on my GCStry wont use that function, unless
> it really wants a physical copy (eg. as buffer, etc)m instead if
> uses G_CSTRY_COPY() which only copies non-static strings.
> 
> > Storing the string as an array of bytes. The first byte of the array
> > would be the "static" bit, and the rest would be the string data.
> 
> Yep, also a good idea. Makes the required stack space smaller than
> my approach. Perhaps could also be extended to do reference counting.
> 
> But: I'm currently lacking sufficient coffeine level to type down
> a typedef+macro that a) makes writing string literals easy and
> b) make it compile-type typesafe.
> 
> Perhaps something like:
> 
> typedef {
>     unsigned char flags;
>     unsigned char str[1];
> } GCStr;
> 
> #define G_CSTR_LITERAL(s) ("\1" s)
> 
> 
> cu

I entertained these 2 approaches a bit and the general slowdown (on my
machine, an i686) resulted in approximately 10-15% overhead in the
following test duplicating strings:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

typedef char *cstr;

typedef struct __attribute__((__packed__)) {
    unsigned int flags;
} cstrinfo;

#define CSTR_STATIC         0x00000001

#define CSTR_INFO(s)        (*(cstrinfo *)((s)-sizeof(cstrinfo)))

#define CSTR_LITERAL(s)     ((cstr)("\x00\x00\x00\x01" s)+sizeof(cstrinfo))
#define CSTR_IS_LITERAL(s)  (CSTR_INFO(s).flags & CSTR_STATIC)

char *_strdup(const char *str)
{
    int len = strlen(str);
    char *r = malloc(len+1);
    memcpy(r, str, len+1);
    return r;
}

void cstrfree(cstr str)
{
    if (CSTR_IS_LITERAL(str)) { return; }
    free(str-sizeof(cstrinfo));
}

cstr cstrdup(const cstr str)
{
    int len = strlen(str);
    cstr r = (cstr)malloc(len+1+sizeof(cstrinfo))+sizeof(cstrinfo);
    memcpy(r, str, len+1);
    CSTR_INFO(r).flags = 0;
    return r;
}

#define DIFF(b, e) \
    (((unsigned long long)(e).tv_sec*1000000000+(unsigned long long)(e).tv_nsec) \
    -((unsigned long long)(b).tv_sec*1000000000+(unsigned long long)(b).tv_nsec))

#define FOO "Hello World!"
int main()
{
    struct timespec start, end;
    char *s = NULL;
    cstr cs = NULL;
    int i, lc;
    unsigned long long fst, snd;
    double d, acc = 0.0;

    for (lc = 1; lc <= 30; ++lc) {
        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
        for (i = 0; i < lc*100000; ++i) {
            if (cs) { cstrfree(cs); }
            cs = cstrdup(CSTR_LITERAL(FOO));
        }
        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
        fst = DIFF(start, end);

        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
        for (i = 0; i < lc*100000; ++i) {
            if (s) { free(s); }
            s = _strdup(FOO);
        }
        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
        snd = DIFF(start, end);

        d = ((double)fst / snd)*100.0-100.0;
        printf("new: %llu ns (%s), old: %llu ns (%s), %.3lf%% increase\n",
               fst, cs, snd, s, d);
        acc += d;
    }
    printf("Average: %lf%%\n", acc/(lc-1));

    cstrfree(cs);
    free(s);

    return 0;
}

Mind you I also tried the explicit approach with a cstr structure
containing a fake char pointer. Results were almost identical. This test
doesn't make use of the features this approach provides, but that wasn't
the point. The overhead arises from working with offsets, so it'll
probably be almost zero in real world cases.

I have however arrived at the conclusion that you should just leave C
strings alone and if it bothers you that much, use a different language
in the future. Frankly, regardless of approach, it will create an
ABI/API nightmare in existing libraries and applications using g_*
functions with strings.