Re: g_utf8_offset_to_pointer() optimization

[Behdad Esfahbod <behdad cs toronto edu>]

Hi there,

Nice job.  As for the time difference between 1 and 1a, b and b1,
it really is more a matter of timing errors.

That said, I like your version 2 approach, but currently it's
wrong: it doesn't pass over the tail of the last characters.

behdad

On Wed, 2 Nov 2005, Luis Menina wrote:

> 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;
> }
>
>
> _______________________________________________
> Performance-list mailing list
> Performance-list gnome org
> http://mail.gnome.org/mailman/listinfo/performance-list
>
>

--behdad
http://behdad.org/

"Commandment Three says Do Not Kill, Amendment Two says Blood Will Spill"
	-- Dan Bern, "New American Language"