Eonblast

Ideally, you want to allocate one buffer beforehand that is large enought to hold the whole eventual JSON string. In practice you can’t know how big that should be unless you go and count first. But for many tables, that one-two punch turns out to be way slower than simply allocating a modest buffer and give it a go, adding more when necessary.

So the basic buffer structure is just that, a potentially more lavish first buffer (called ‘lucky’ in the source because you are lucky, performance-wise, if that buffer turns out big enough). And then smaller buffers that are allocated when you need them. You can tweak their size in fleece-intern.h for now. There should be parameters for that at some point.

The aim is to touch each bit of data only once, or twice if need be. The second touching being the eventual concatenating of the buffers to return the result back to Lua. If the ‘lucky’ buffer was lucky and big enough, even that step is skipped.

After the buffer mechanism had reached a stable condition, half of it was turned into macros to ‘inline’ them. A function call basically only takes place when a new, additional buffer has to be created. All writing usually takes place using macros, copying directly onto the current buffer.

To reduce repetitive calculations on remaining buffer sizes, the buffer is operated on the assumption that it must always have three reserve characters left, on top of what other space reserve it is tested for at any time. These tests are taking place before a Lua value’s string representation is written into the buffer. The reserve space can then be ‘blindly’ used up for two of ‘,:”"‘. Only two of these ever appear consecutively in a JSON string, before the next actual value, or a bracket is written. During which the next reserve space is taken care of, for the next ‘punctuation’ characters. To maintain this tacit assurance saves a lot of cycles, because the buffer size calculations before writing ‘,:”"‘ can be dropped altogether.

Replacing C memcpy by a native C variant showed gains on a slower machine but Fleece is to be optimized for servers. What turned out to be efficient though, is a Duff’s Device-like switch that casts memory areas into structures and by that tries to make C optimize the moving of small memory blocks at compile time. This looks funny but works quite well. It can come to bear quite heavily since especially string table keys are often short. For longer blocks, the C memcpy implementation, as was to be expected, turns out to be the most efficient. You can find the complete buffer handling source at:
https://github.com/Eonblast/fleece-lite/blob/master/src/fleece-buffers.c and https://github.com/Eonblast/fleece-lite/blob/master/src/fleece-buffers.h

Faster Memcpy fleece-buffers.h

struct char2  { char mem[2]; };  typedef struct char2 *buf2;
struct char3  { char mem[3]; };  typedef struct char3 *buf3;
struct char4  { char mem[4]; };  typedef struct char4 *buf4;
struct char5  { char mem[5]; };  typedef struct char5 *buf5;
struct char6  { char mem[6]; };  typedef struct char6 *buf6;
struct char7  { char mem[7]; };  typedef struct char7 *buf7;
struct char8  { char mem[8]; };  typedef struct char8 *buf8;
struct char9  { char mem[9]; };  typedef struct char9 *buf9;
struct char10 { char mem[10]; }; typedef struct char10 *buf10;
struct char11 { char mem[11]; }; typedef struct char11 *buf11;
struct char12 { char mem[12]; }; typedef struct char12 *buf12;
struct char13 { char mem[13]; }; typedef struct char13 *buf13;
struct char14 { char mem[14]; }; typedef struct char14 *buf14;
struct char15 { char mem[15]; }; typedef struct char15 *buf15;
struct char16 { char mem[16]; }; typedef struct char16 *buf16;

#define fast_memcpy_macro(_dest, _src, _count) { \
\
	if(_count<=16) { \
		switch(_count) { \
		case 1:  *(char*)_dest = *(char*)_src; break; \
		case 2:  *(buf2)_dest  = *(buf2)_src;  break; \
		case 3:  *(buf3)_dest  = *(buf3)_src;  break; \
		case 4:  *(buf4)_dest  = *(buf4)_src;  break; \
		case 5:  *(buf5)_dest  = *(buf5)_src;  break; \
		case 6:  *(buf6)_dest  = *(buf6)_src;  break; \
		case 7:  *(buf7)_dest  = *(buf7)_src;  break; \
		case 8:  *(buf8)_dest  = *(buf8)_src;  break; \
		case 9:  *(buf9)_dest  = *(buf9)_src;  break; \
		case 10: *(buf10)_dest = *(buf10)_src; break; \
		case 11: *(buf11)_dest = *(buf11)_src; break; \
		case 12: *(buf12)_dest = *(buf12)_src; break; \
		case 13: *(buf13)_dest = *(buf13)_src; break; \
		case 14: *(buf14)_dest = *(buf14)_src; break; \
		case 15: *(buf15)_dest = *(buf15)_src; break; \
		case 16: *(buf16)_dest = *(buf16)_src; break; \
		} \
	} \
	else { \
		memcpy(_dest, _src, _count); \
    } \
}

For completeness, the faster mempy replacement, for a slow machine (Apple PPC) was:

void fast_memcpy(char *dest, const char* src, size_t count) {

	char* dst8 = (char*)dest;
	char* src8 = (char*)src;
    --src8;
    --dst8;
        
    while (count--)
       *++dst8 = *++src8;
}

I am afraid I lost the reference where I got it from. There is some intelligent reasoning behind it, as to why it is done this way. In any event, it is not used in Fleece, as for faster CPUs it seemed to be slower than gcc memcpy.

Another measure that resulted in significant gains was to pull the counting and copying of a string into one. Since counting becomes only relevant when characters are present that need to be escaped (otherwise destination length will equal source length), the idea was that the loop over the string could be used to both count and copy. In the case that too many control characters are encountered, the copying is canceled, only the counting is continued to the end. Sufficient buffer is then allocated to cope with the string to be added and the copying is restarted. This time, without counting. This is separated into individual maximally fast functions, which pays off for this really hot spot. It is actually completely optimized only in the x86 inline assembler version, which presents the final optimization step.

Number conversion

Finally, number conversion algorithms play a role in JSON string creation.

The overall strategy concerning numbers is:

The standard way to produce the string representation of a number is using sprintf(). As could be expected, that introduces overhead that is not needed and not wanted at such a central place in the loop. If you encode a million numbers, obviously every cycle saved is worth a million cycles, so this deserved attention.

Fleece comes with four additional functions that can emulate sprintf(). But for compatibility, you can also make it use sprintf() and be sure to get a more standard conformant result. At present, you can change the default precision only at compile time by changing the constant in fleece-intern.h.

Don't give too much credit to the standard here: standards in floating point conversions, and their internal representation, are a bit screwed up. So not following the standard in this case may be less daring than it may sound.

Fleece also takes care of floats that have no decimal fraction, by casting them into ints and then using the faster integer to ASCII conversion.

And it creates two internal look up tables of numbers 1 through 999 to avoid divisions in the conversion of integers in the range of - to +1,000,000. The tables allow for the replacement of up to three costly divisions by one single, much faster pointer addition. Fleece allocates and fills two 4K tables for this and leaves these tables up once created. In a future version there should be an option to switch the use or the keeping of these tables off. For integers outside the range of -+1M, a 'normal' division strategy is applied.

The integer conversion looks like the following code snippet. I trimmed some comments and assertions. You can find the original source here:

https://github.com/Eonblast/fleece-lite/blob/master/src/fleece-numbers.c

Integer Conversion fleece-numbers.c

void itoa(int pvalue, char* pstr, size_t *rlen) {

	static char num[] = "0123456789";

	int value = pvalue;
	char *str = pstr;

	// take care of sign
	if(value<0) { *str++ = '-'; value = -value; }

	/* -999 - +999 */

	if (value<1000) {
		if(!mux) initmux();
		char *q = mux + value*4;
		char qq;
		*str++=*q++; if(qq=*q++) { *str++=qq; if(qq=*q++) { *str++=qq; } }
		*str=0;
		*rlen = str - pstr;
		goto ret;
	}

	if (value<1000000) {
		if(!mux) initmux();
		char *q = mux + (value/1000*4);
		char qq;
		*(str++)=*q++; if(qq=*q++) { *(str++)=qq; if(qq=*q++) { *(str++)=qq; } }
		value %= 1000;
		q = mux0 + (4*value);
		*str++=*q++;
		*str++=*q++;
		*str++=*q++;
		*str=0;
		*rlen = str - pstr;
		goto ret;
	}

	/* #4 any length
	   Source: Stuart Lowe's optimization of the Kernighan & Ritchie sample
       at http://www.strudel.org.uk/itoa/ */	

	char* wstr=str;
	int sign;
	div_t res;

	// Conversion. Number is reversed.
	do {
		res = div(value,10);
		*wstr++ = num[res.rem];
	} while((value=res.quot));

	if(sign<0) *wstr++='-';
	*wstr='\0';
	*rlen = wstr - pstr;

	strreverse(str,wstr-1);

	ret:;
	...
	return;
}

This concludes our trip through the inner workings of Fleece. Thanks for your interest, I'll be happy to hear back from you.

Henning

[1] Duff's Device: http://en.wikipedia.org/wiki/Duff's_device