Re: g_utf8_offset_to_pointer() optimization

[Luis Menina <liberforce fr st>]

Thanks Behdad,

About the timing errors, I surely performed lots and lots of tests, and 
had always the same results... Sometimes the version with the shift and 
the checkings was even *faster* than the one without checking (when I 
had my signed/unsigned char problem) ... I don't know what gcc is doing 
behind this...


Can you give me more info about what is wrong with my function ?
I don't understand what you mean by "it doesn't pass over the tail of 
the last characters"

Behdad Esfahbod a écrit :
> 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"