g_utf8_offset_to_pointer() optimization

[Luis Menina <liberforce fr st>]

Well, federico asked here (
http://primates.ximian.com/~federico/news-2005-10.html#31 ) for a
volonteer, so here I am :-p


After a lot of tests, the winners are versions 2 (without parameter
check) and 2a (with paramter check), even if 2a is faster (?!!!) than
2... I don't know why, so if someone knows, i'll really apreciate some
explanations :-)

The original g_utf8_offset_to_pointer is 6.71s on my computer. My best
shot (version 2a) is 3.45s.

The tricky part was to figure out why with the bit shifting I had 
incorrect results: just because character spread on multiple bytes are 
negative values for a char... so when shifting the bits, the signed 
value was completed by ones and not zeros on the left... sic...

That's why the guchar cast is so important... Lost sooo much time with 
this... Damn, I'll do better next time ^_^

Compiled with GCC 4.0.1 with -02 flag on a Athlon XP3000+ machine

======================================================


/* -*-coding: utf-8;-*- */

#include <gtk/gtk.h>


/* After a lot of tests, the winners are versions 2 (without parameter
check)
* and 2a (with paramter check), even if 2a is faster (?!!!) than 2...
*/

const gchar *longline = "asdasdas dsaf asfd as fdasdf asfd asdf as dfas
dfasdf a\
asd fasdf asdf asdf asd fasfd as fdasfd asdf as fdççççççççças
ffsd asfd as fdASASASAs As\
Asfdsf sdfg sdfg dsfg dfg sdfgsdfgsdfgsdfg sdfgsdfg sdfg sdfg sdf gsdfg
sdfg sd\
asd fasdf asdf asdf asd fasfd as fdaÚÚÚÚÚÚÚ
òòòòòòòòòòòòsfd asdf as fdas ffsd asfd as fdASASASAs D \
Asfdsf sdfg sdfg dsfg dfg sdfgsdfgsdfgsdfg sdfgsdfg
sdfgùùùùùùùùùùùùùù sdfg sdf gsdfg sdfg sd\
asd fasdf asdf asdf asd fasfd as fdasfd asd@@@@@@@f as fdas ffsd asfd as
fdASASASAs D \
Asfdsf sdfg sdfg dsfg dfg
sdfgsdfgsdfgsdfg
sdfgsdf€€€€€€€€€€€€€€€€€€g sdfg sdfg
sdf gsdfg sdfg sd\
asd fasdf asdf asdf asd fasfd as fdasfd asdf as fdas ffsd asfd as
fdASASASAs D \
Asfdsf sdfg sdfg dsfg dfg sdfgsdfgsdfgsdfg sdfgsdfg sdfg sdfg sdf gsdfg
sdfg sd\
\n\nlalala\n";

/* original: 6.71 s */
gchar * g_utf8_offset_to_pointer0 (	const gchar *str,
                          		glong offset)
{
	const gchar *s = str;
	while (offset--)
	s = g_utf8_next_char (s);

	return (gchar *)s;
}

/* 6.71
* Try:
* - Tell gcc to use registers
*
* Comment:
* no improvement, the -02 option must perform such optimizations
* 'register' here is useless
*/
gchar * g_utf8_offset_to_pointer0a (	register const gchar *str,
                          		register glong offset)
{
	const gchar *s = str;
	while (offset--)
	s = g_utf8_next_char (s);

	return (gchar *)s;
}

/* 6.70s
* Try:
* - Use directly the str var instead of creating another one...
*
* Comment:
* no improvement, the -02 option must perform such optimizations
* this is useless, but best practice...
*/
gchar * g_utf8_offset_to_pointer0b (	const gchar *str,
					glong offset)
{
	while (offset--)
		str = g_utf8_next_char (str);
	
	return (gchar *)str;
}

/* 3.55s
* Try:
* - The property used is that in a well formed UTF8 string, every byte that
* doesn't start with the bits '10' marks the beginning of an UTF8 character.
* - Uses a bit mask to identify bytes that are not at the beginning of a
* UTF8 character
*
* Comment:
* really improves the performance, but maybe we can do better...
*/
gchar * g_utf8_offset_to_pointer1 (	const gchar *str,
					glong offset)
{
	while (offset)
	{
		if ((*++str & 0xC0) != 0x80)
			--offset ;
	}
	
	return (gchar *)str;
}

/* 4.12s
* Try:
* - Use the bitmask version and add the parameter checks
*
* Comment:
* 1a is slower than version 1 which seems normal,
* because there's more code executed... Still don't know
* why 2a is faster than 2...
*
*/
gchar * g_utf8_offset_to_pointer1a (	const gchar *str,
					glong offset)
{
	g_return_val_if_fail (str !=  NULL,  NULL);
	g_return_val_if_fail (offset > 0, (gchar *)str);

	while (offset)
	{
		if ((*++str & 0xC0) != 0x80)
			--offset ;
	}
	
	return (gchar *)str;
}

/* 3.45s
* Try:
* - Same algorithm used for character detecttion
*
* Comment:
* good bet ! a simple bit shift is better than a mask
*/
gchar * g_utf8_offset_to_pointer2 (	const gchar *str,
					glong offset)
{
	while (offset)
	{
		if (((guchar)(*++str) >> 6) != 0x02)
			--offset ;
	}
	
	return (gchar *)str;
}

/* 3.45s - <<<<< THE BEST ONE >>>>>>
* Try:
* - Just add some parameter checking
*
* Comments:
* I don't understand this - adding some code, I have the same
* performance, wheras in the version 1 => 1a switch I lose some !!!
*/
gchar * g_utf8_offset_to_pointer2a (	const gchar *str,
					glong offset)
{
	g_return_val_if_fail (str !=  NULL,  NULL);
	g_return_val_if_fail (offset > -1, (gchar *)str);
	
	while (offset)
	{
		if (((guchar)(*++str) >> 6) != 0x02)
			--offset ;
	}
	
	return (gchar *)str;
}



int
main (int argc, char **argv)
{
	int i;
	gulong len;
	const gchar *old, *c, *c1;

	gtk_init (&argc, &argv);

	len = g_utf8_strlen(longline, -1);

	/* Test result validy */
	for (i = 1, c = longline; i < len; ++i)
	{
		old = c;
		c  = g_utf8_offset_to_pointer(longline, i);

		/* Change here the name of the function to check for validity */
		c1 = g_utf8_offset_to_pointer2(longline, i);


		if (c != c1)
		{

			printf("at [%d], %p <=> %p : jump = %d \n", (int)i, c, c1, c-old);
			printf("at [%d], %02X \n", (int)i-4, (char)*(c-4));
			printf("at [%d], %02X \n", (int)i-3, (char)*(c-3));
			printf("at [%d], %02X \n", (int)i-2, (char)*(c-2));
			printf("at [%d], %02X \n", (int)i-1, (char)*(c-1));
			printf("at [%d], %02X \n", (int)i  , (char)*c    );
			g_assert_not_reached();
		}
	}
	
	/* Test performance */
	for (i = 0; i < 2000000 ; ++i)
	{
		/* Change here the name of the function to profile */
		c = g_utf8_offset_to_pointer2(longline, len);
	}

	return 0;
}