Re: [bug-gnulib] new module mpsort for faster sorting
Hello Paul, Such a function can lead to faster execution in some important cases, as I have verified using GNU 'ls' as a guinea pig. Does the speedup come from the use of the mergesort algorithm, or from avoiding a function call in the comparison function (with qsort, the pointer indirection must be done inside the comparison function; here it's done outside)? Bruno
Re: new module mpsort for faster sorting
Bruno Haible [EMAIL PROTECTED] wrote: Hello Paul, Such a function can lead to faster execution in some important cases, as I have verified using GNU 'ls' as a guinea pig. Does the speedup come from the use of the mergesort algorithm, or from avoiding a function call in the comparison function (with qsort, the pointer indirection must be done inside the comparison function; here it's done outside)? Hi Bruno, When sorting records larger than a pointer, reduced data movement is likely to be the overriding factor: better use of cache. I.e., setting up the array of pointers costs just O(N) time and memory, but you save O(N log(N)) time in reduced data copying costs, because mpsort is swapping only pointers, whereas qsort swaps the entire (larger) records. So, for small N and/or very small record size, there may be a small run-time performance decrease, but for all other cases, there should be an improvement. Based on my minimal experience, I suspect that GNU sort will end up using mpsort, too.
Re: new module mpsort for faster sorting
Jim Meyering wrote:
When sorting records larger than a pointer, reduced data movement is
likely to be the overriding factor: better use of cache.
I.e., setting up the array of pointers costs just O(N) time and memory,
but you save O(N log(N)) time in reduced data copying costs, because
mpsort is swapping only pointers, whereas qsort swaps the entire (larger)
records.
This is undoubtable.
My question is: Once you have switched from an array representation with
sizeof (element) sizeof (void *) to an array representation with
sizeof (element) == sizeof (void *), you still have 3 ways to sort:
a) with qsort and a comparison function that does
int cmp (void **p, void **q) { return element_cmp (*p, *q); }
b) with a mergesort implementation that looks like mpsort, but calls
cmp (ba, bb)
instead of
cmp (ba, bb)
and instead does the indirection in the comparison function:
int cmp (void **p, void **q) { return element_cmp (*p, *q); }
c) with the mpsort function as it is, and element_cmp as the comparison
function.
Does the major speedup come from the transition a) - b), or from the
transition b) - c) ?
Bruno
[PATCH]: strptime module
Hi,
Here is a GnuLib module providing the strptime function, merged from the
glibc implementation. From my minor testing, the module seem to work.
Regards,
--
Yoann Vandoorselaere [EMAIL PROTECTED]
Index: lib/strptime.c
===
RCS file: lib/strptime.c
diff -N lib/strptime.c
--- /dev/null 1 Jan 1970 00:00:00 -
+++ lib/strptime.c 29 Jan 2007 11:58:53 -
@@ -0,0 +1,1147 @@
+/* Copyright (C) 2002, 2004, 2005 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, write to the Free
+ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307 USA. */
+
+#ifdef HAVE_CONFIG_H
+# include config.h
+#endif
+
+#undef _LIBC
+#undef _NL_CURRENT
+
+#include sys/time.h
+#include assert.h
+#include ctype.h
+#ifdef _LIBC
+# include langinfo.h
+#endif
+#include limits.h
+#include string.h
+#include time.h
+#include stdbool.h
+
+#ifdef _LIBC
+# include ../locale/localeinfo.h
+#endif
+
+#include stdlib.h
+#include strptime.h
+#include time_r.h
+
+
+enum ptime_locale_status { not, loc, raw };
+
+
+#ifndef __P
+# if defined __GNUC__ || (defined __STDC__ __STDC__)
+# define __P(args) args
+# else
+# define __P(args) ()
+# endif /* GCC. */
+#endif /* Not __P. */
+
+
+
+#define match_char(ch1, ch2) if (ch1 != ch2) return NULL
+
+# define match_string(cs1, s2) \
+ (strncasecmp ((cs1), (s2), strlen (cs1)) ? 0 : ((s2) += strlen (cs1), 1))
+
+/* We intentionally do not use isdigit() for testing because this will
+ lead to problems with the wide character version. */
+#define get_number(from, to, n) \
+ do { \
+int __n = n; \
+val = 0; \
+while (*rp == ' ') \
+ ++rp; \
+if (*rp '0' || *rp '9') \
+ return NULL; \
+do { \
+ val *= 10; \
+ val += *rp++ - '0'; \
+} while (--__n 0 val * 10 = to *rp = '0' *rp = '9'); \
+if (val from || val to) \
+ return NULL; \
+ } while (0)
+#ifdef _NL_CURRENT
+# define get_alt_number(from, to, n) \
+ ({ \
+ __label__ do_normal; \
+ \
+ if (*decided != raw) \
+ { \
+ val = _nl_parse_alt_digit (rp HELPER_LOCALE_ARG); \
+ if (val == -1 *decided != loc) \
+ { \
+ *decided = loc; \
+ goto do_normal; \
+ } \
+ if (val from || val to) \
+ return NULL; \
+ } \
+ else \
+ { \
+ do_normal: \
+ get_number (from, to, n); \
+ } \
+0; \
+ })
+#else
+# define get_alt_number(from, to, n) \
+ /* We don't have the alternate representation. */ \
+ get_number(from, to, n)
+#endif
+#define recursive(new_fmt) \
+ (*(new_fmt) != '\0' \
+(rp = __strptime_internal (rp, (new_fmt), tm, \
+ decided, era_cnt LOCALE_ARG)) != NULL)
+
+
+#ifdef _LIBC
+/* This is defined in locale/C-time.c in the GNU libc. */
+extern const struct locale_data _nl_C_LC_TIME attribute_hidden;
+
+# define weekday_name (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (DAY_1)].string)
+# define ab_weekday_name \
+ (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (ABDAY_1)].string)
+# define month_name (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (MON_1)].string)
+# define ab_month_name (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (ABMON_1)].string)
+# define HERE_D_T_FMT (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (D_T_FMT)].string)
+# define HERE_D_FMT (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (D_FMT)].string)
+# define HERE_AM_STR (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (AM_STR)].string)
+# define HERE_PM_STR (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (PM_STR)].string)
+# define HERE_T_FMT_AMPM \
+ (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (T_FMT_AMPM)].string)
+# define HERE_T_FMT (_nl_C_LC_TIME.values[_NL_ITEM_INDEX (T_FMT)].string)
+
+# define strncasecmp(s1, s2, n) __strncasecmp (s1, s2, n)
+#else
+static char const weekday_name[][10] =
+ {
+Sunday, Monday, Tuesday, Wednesday,
+Thursday, Friday, Saturday
+ };
+static char const ab_weekday_name[][4] =
+ {
+Sun, Mon, Tue, Wed,
Re: gnulib-tool and line length: gl_LIBOBJS
* Bruno Haible wrote on Sun, Jan 28, 2007 at 05:00:08PM CET: Ralf Wildenhues wrote: Adding newlines and backslashes to an AC_SUBSTed value limits its use: It can only be used in particular places of Makefiles. Which other places do you need gl_LIBOBJ at? Sorry, I fail to see the problem here. The problem is maintainability (someday we may want to use @gl_LIBOBJS@ directly in the statements of a Makefile rule, for example), and walking on thin ice (newlines and backslashes inside AC_SUBSTed values are risky). You can simply use $(gl_LIBOBJS) instead of @[EMAIL PROTECTED] Problem solved: backslash-newline outside of a rule command line is replaced with a single space by 'make'. In the long run you are IMVHO hindering maintainability by allowing such usages now, instead of having them found early and eliminated. But I'll stop insisting now, do as you please. ;-) Cheers, Ralf
Re: memrchr on cygwin
Eric Blake wrote: OK to apply this? 2007-01-29 Eric Blake [EMAIL PROTECTED] * lib/memrchr.c: Assume string.h unconditionally, to pull in size_t as needed. Yes, this is OK. Usually when one needs size_t, including stddef.h is the preferred choice, because it defines a minimum of declarations. But here the problem actually is that memchr.c doesn't include its specification header string.h. Thank you for shaking out this problem so quickly! Bruno
Re: [PATCH]: strptime module
Thanks. I installed these further patches to try to keep this module
in sync with POSIX and glibc as much as possible. I haven't tested
this on a Windows platform, though; please let me know if there are
any problems.
2007-01-29 Paul Eggert [EMAIL PROTECTED]
* lib/strptime.h (strptime): Use 'restrict' for args where
POSIX requires this.
* lib/strptime.c (strptime): Likewise.
Change license notice from LGPL to GPL, since gnulib-tool will
change this as needed.
Include config.h if _LIBC is not defined, not if HAVE_CONFIG_H is
defined.
Include strptime.h first, to check interface.
Do not #undef _LIBC and _NL_CURRENT.
Do not include stdlib.h; no longer needed.
Include time_r.h and declare ptime_locale_status
only if _LIBC is not defined.
(__P): Remove unused macro.
(match_string): Bring back glibc version, but use it only if _LIBC
is defined.
(__strptime_internal): Compile tm_gmtoff code if _LIBC is defined, too.
Remove unnecessary assertion and abort() call.
Use #ifdef _NL_CURRENT rather than #if 0, for benefit of glibc.
* m4/strptime.m4: Fix serial number comment.
(gl_FUNC_STRPTIME): Require AC_C_RESTRICT, gl_TM_GMTOFF.
* modules/strptime (Files): Add m4/tm_gmtoff.m4.
(Depends-on): Add time_r.
Index: lib/strptime.h
===
RCS file: /cvsroot/gnulib/gnulib/lib/strptime.h,v
retrieving revision 1.2
diff -u -p -r1.2 strptime.h
--- lib/strptime.h 29 Jan 2007 17:33:13 - 1.2
+++ lib/strptime.h 29 Jan 2007 23:12:51 -
@@ -23,7 +23,8 @@
#if ! HAVE_STRPTIME
/* See the POSIX:2001 specification
http://www.opengroup.org/susv3xsh/strptime.html. */
-extern char *strptime (const char *s, const char *format, struct tm *tm);
+extern char *strptime (const char *restrict s, const char *restrict format,
+ struct tm *restrict tm);
#endif
#endif /* GNULIB_STRPTIME_H_ */
Index: lib/strptime.c
===
RCS file: /cvsroot/gnulib/gnulib/lib/strptime.c,v
retrieving revision 1.1
diff -u -p -r1.1 strptime.c
--- lib/strptime.c 29 Jan 2007 17:21:16 - 1.1
+++ lib/strptime.c 29 Jan 2007 23:12:52 -
@@ -1,29 +1,25 @@
-/* Copyright (C) 2002, 2004, 2005 Free Software Foundation, Inc.
+/* Copyright (C) 2002, 2004, 2005, 2007 Free Software Foundation, Inc.
This file is part of the GNU C Library.
- The GNU C Library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public
- License as published by the Free Software Foundation; either
- version 2.1 of the License, or (at your option) any later version.
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
- The GNU C Library is distributed in the hope that it will be useful,
+ This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Lesser General Public License for more details.
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
- You should have received a copy of the GNU Lesser General Public
- License along with the GNU C Library; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307 USA. */
+ You should have received a copy of the GNU General Public License along
+ with this program; if not, write to the Free Software Foundation,
+ Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
-#ifdef HAVE_CONFIG_H
+#ifndef _LIBC
# include config.h
+# include strptime.h
#endif
-#undef _LIBC
-#undef _NL_CURRENT
-
-#include sys/time.h
#include assert.h
#include ctype.h
#ifdef _LIBC
@@ -38,29 +34,25 @@
# include ../locale/localeinfo.h
#endif
-#include stdlib.h
-#include strptime.h
-#include time_r.h
-
-
+#ifndef _LIBC
+# include time_r.h
enum ptime_locale_status { not, loc, raw };
-
-
-#ifndef __P
-# if defined __GNUC__ || (defined __STDC__ __STDC__)
-# define __P(args) args
-# else
-# define __P(args) ()
-# endif /* GCC. */
-#endif /* Not __P. */
+#endif
#define match_char(ch1, ch2) if (ch1 != ch2) return NULL
-
+#if defined _LIBC defined __GNUC__ __GNUC__ = 2
+# define match_string(cs1, s2) \
+ ({ size_t len = strlen (cs1);
\
+ int result = __strncasecmp_l ((cs1), (s2), len, locale) == 0; \
+ if (result) (s2) += len;\
+ result; })
+#else
+/*
