Andrew Dunstan wrote:
Another question that occurred to me - did you try using strpbrk() to look for the next interesting character rather than your homegrown searcher gadget? If so, how did that perform?
It looks like strpbrk() performs poorly: unpatched: testname | min duration ----------+----------------- all | 00:00:08.099656 1/2 | 00:00:06.734241 1/4 | 00:00:06.016946 1/8 | 00:00:05.622122 1/16 | 00:00:05.304252 none | 00:00:05.155755 (6 rows) strpbrk: testname | min duration ----------+----------------- all | 00:00:22.980997 1/2 | 00:00:13.724834 1/4 | 00:00:08.980246 1/8 | 00:00:06.582357 1/16 | 00:00:05.291485 none | 00:00:06.239468 (6 rows) memchr: testname | min duration ----------+----------------- all | 00:00:13.684479 1/2 | 00:00:09.509213 1/4 | 00:00:06.921959 1/8 | 00:00:05.654761 1/16 | 00:00:04.719027 none | 00:00:03.718361 (6 rows)Attached is the test script and patches I used, if someone wants to test this on another platform.
-- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com
Index: src/backend/commands/copy.c
===================================================================
RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/commands/copy.c,v
retrieving revision 1.295
diff -c -r1.295 copy.c
*** src/backend/commands/copy.c 1 Jan 2008 19:45:48 -0000 1.295
--- src/backend/commands/copy.c 5 Mar 2008 14:44:58 -0000
***************
*** 67,72 ****
--- 67,275 ----
EOL_CRNL
} EolType;
+
+ /***** Fast byte searcher functions *****
+ *
+ * CopyReadLine needs to search for newlines, as well as quoting and escape
+ * characters to determine which newlines are real and which ones are escaped.
+ * Doing that in the naive way, looping through the input byte by byte and
+ * comparing against the interesting characters, can be slow.
+ *
+ * To speed that up, we provide a "searcher" interface, that can be used to
+ * search a piece of memory for up to 4 different bytes simultaneously. It's
+ * similar to memchr, but allows searching for multiple chars at the same
+ * time.
+ *
+ * To start a search on a new block of memory, call init_searcher. Then call
+ * next_searcher repeatedly to return all the occurrances of the bytes being
+ * searched for.
+ *
+ * The searcher implementation uses memchr to search for the bytes, and keeps
+ * track of where the next occurrance of each is. Using memchr allows us
+ * to take advantage of any platform-specific optimizations.
+ */
+
+ /*
+ * Struct used to store state of the current search between calls to
+ * next_searcher. Initialized by init_search.
+ */
+ typedef struct {
+ /* Each element in c corresponds the element in s. These are sorted
+ * by the pointers (ptr) */
+ int n; /* elements used in the arrays */
+ char c[4]; /* bytes we're looking for */
+ char *ptr[4]; /* pointers to next occurances of the bytes */
+ char *end; /* end of block being searched. Last byte to search is end-1 */
+ } searcher;
+
+ /* Functions internal to "searcher" */
+
+ #define swap_searcher_entries(searcher, a, b) do { \
+ char tmpc = (searcher)->c[a]; \
+ char *tmpptr = (searcher)->ptr[a]; \
+ (searcher)->c[a] = (searcher)->c[b]; \
+ (searcher)->ptr[a] = (searcher)->ptr[b]; \
+ (searcher)->c[b] = tmpc; \
+ (searcher)->ptr[b] = tmpptr; \
+ } while(0)
+
+ static void
+ sort_searcher(searcher *s)
+ {
+ switch(s->n)
+ {
+ case 0:
+ case 1:
+ /* Nothing to do */
+ break;
+ case 2:
+ if (s->ptr[0] > s->ptr[1])
+ swap_searcher_entries(s, 0, 1);
+ break;
+ case 3:
+ if (s->ptr[0] > s->ptr[2])
+ swap_searcher_entries(s, 0, 2);
+ if (s->ptr[0] > s->ptr[1])
+ swap_searcher_entries(s, 0, 1);
+ if (s->ptr[1] > s->ptr[2])
+ swap_searcher_entries(s, 1, 2);
+ break;
+ case 4:
+ if (s->ptr[0] > s->ptr[1])
+ swap_searcher_entries(s, 0, 1);
+ if (s->ptr[2] > s->ptr[3])
+ swap_searcher_entries(s, 2, 3);
+ if (s->ptr[1] > s->ptr[2])
+ swap_searcher_entries(s, 2, 3);
+ if (s->ptr[0] > s->ptr[1])
+ swap_searcher_entries(s, 0, 1);
+ if (s->ptr[2] > s->ptr[3])
+ swap_searcher_entries(s, 2, 3);
+ break;
+ }
+ }
+
+ /* Remove the topmost element */
+ static void
+ remove_top(searcher *searcher)
+ {
+ int i;
+
+ searcher->n--;
+
+ /* Move up the remaining items */
+ for (i = 0; i < searcher->n; i++)
+ {
+ searcher->c[i] = searcher->c[i + 1];
+ searcher->ptr[i] = searcher->ptr[i + 1];
+ }
+ }
+
+ /*
+ * The first element in the list has been replaced by the caller.
+ * Move it to the right place in the list, to keep it sorted.
+ */
+ static void
+ sift_down(searcher *searcher)
+ {
+ if (searcher->n < 2 || searcher->ptr[0] <= searcher->ptr[1])
+ return;
+ swap_searcher_entries(searcher, 0, 1);
+
+ if (searcher->n < 3 || searcher->ptr[1] <= searcher->ptr[2])
+ return;
+ swap_searcher_entries(searcher, 1, 2);
+
+ if (searcher->n < 4 || searcher->ptr[2] <= searcher->ptr[3])
+ return;
+ swap_searcher_entries(searcher, 2, 3);
+ }
+
+ /*
+ * Starts a new search in a block of memory.
+ *
+ * searcher - for storing state between calls. Opaque to caller,
+ * init_searcher will initialize this.
+ * str - block of memory to search
+ * len - length of str
+ * c - bytes to search for, max 4.
+ * n - number of bytes in c
+ */
+ static void
+ init_searcher(searcher *searcher, char *str, int len, char c[4], int n)
+ {
+ int i;
+
+ Assert(n <= 4);
+
+ searcher->n = 0;
+ searcher->end = str + len;
+
+ /* Find first occurances of the searched-for bytes */
+ for (i = 0; i < n; i++)
+ {
+ char *hit = memchr(str, c[i], len);
+ if (hit != NULL)
+ {
+ searcher->c[searcher->n] = c[i];
+ searcher->ptr[searcher->n] = hit;
+ searcher->n++;
+ }
+ /*
+ * If the byte doesn't occur in the string at all, we don't
+ * need to put it in the list.
+ */
+ }
+ sort_searcher(searcher);
+ }
+
+ /*
+ * Look for the next interesting character
+ *
+ * searcher - state, opaque to caller
+ * str - block to search.
+ *
+ * 'str' must be part of the block passed to init_searcher, and >=
+ * the return value of last call to next_searcher.
+ *
+ * Returns the offset of the next interesting location, relative to 'ss'
+ */
+ static char *
+ next_searcher(searcher *searcher, char *str)
+ {
+ Assert(str < searcher->end);
+
+ if (searcher->n == 0)
+ return NULL;
+
+ /*
+ * If the caller skipped over the next pointer we had memorized, we have to
+ * search for the one after that.
+ */
+ while (str > searcher->ptr[0])
+ {
+ char *s = memchr(str, searcher->c[0], searcher->end - str);
+
+ if (s == NULL)
+ {
+ remove_top(searcher);
+ if (searcher->n == 0)
+ return NULL;
+ }
+ else
+ {
+ searcher->ptr[0] = s;
+ sift_down(searcher);
+ }
+ }
+
+ /*
+ * Return the next interesting location we had memorized.
+ */
+ return searcher->ptr[0];
+ }
+
+
/*
* This struct contains all the state variables used throughout a COPY
* operation. For simplicity, we use the same struct for all variants of COPY,
***************
*** 159,164 ****
--- 362,369 ----
char *raw_buf;
int raw_buf_index; /* next byte to process */
int raw_buf_len; /* total # of bytes stored */
+
+ searcher searcher;
} CopyStateData;
typedef CopyStateData *CopyState;
***************
*** 2285,2299 ****
--- 2490,2516 ----
last_was_esc = false;
char quotec = '\0';
char escapec = '\0';
+ char search_chars[4];
+ int nsearch_chars = 0;
+
+ search_chars[nsearch_chars++] = '\n';
+ search_chars[nsearch_chars++] = '\r';
if (cstate->csv_mode)
{
quotec = cstate->quote[0];
escapec = cstate->escape[0];
+
+ search_chars[nsearch_chars++] = quotec;
+
/* ignore special escape processing if it's the same as quotec */
if (quotec == escapec)
escapec = '\0';
+ else
+ search_chars[nsearch_chars++] = escapec;
}
+ else
+ search_chars[nsearch_chars++] = '\\';
mblen_str[1] = '\0';
***************
*** 2360,2368 ****
--- 2577,2603 ----
break;
}
need_data = false;
+
+ if (!cstate->encoding_embeds_ascii)
+ init_searcher(&cstate->searcher, copy_raw_buf, copy_buf_len,
+ search_chars, nsearch_chars);
}
/* OK to fetch a character */
+ if ((!cstate->csv_mode || !first_char_in_line)
+ && !cstate->encoding_embeds_ascii
+ && (raw_buf_ptr + 4 <= copy_buf_len))
+ {
+ char *next = next_searcher(&cstate->searcher,
+ ©_raw_buf[raw_buf_ptr]);
+
+ if (next != NULL)
+ {
+ raw_buf_ptr = next - copy_raw_buf;
+ first_char_in_line = false;
+ }
+ }
+
prev_raw_ptr = raw_buf_ptr;
c = copy_raw_buf[raw_buf_ptr++];
Index: src/backend/commands/copy.c
===================================================================
RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/commands/copy.c,v
retrieving revision 1.296
diff -c -r1.296 copy.c
*** src/backend/commands/copy.c 8 Mar 2008 01:16:26 -0000 1.296
--- src/backend/commands/copy.c 9 Mar 2008 09:34:13 -0000
***************
*** 2285,2299 ****
--- 2285,2311 ----
last_was_esc = false;
char quotec = '\0';
char escapec = '\0';
+ char search_chars[5] = { 0, 0, 0, 0, 0 };
+ int nsearch_chars = 0;
+
+ search_chars[nsearch_chars++] = '\n';
+ search_chars[nsearch_chars++] = '\r';
if (cstate->csv_mode)
{
quotec = cstate->quote[0];
escapec = cstate->escape[0];
+
+ search_chars[nsearch_chars++] = quotec;
+
/* ignore special escape processing if it's the same as quotec */
if (quotec == escapec)
escapec = '\0';
+ else
+ search_chars[nsearch_chars++] = escapec;
}
+ else
+ search_chars[nsearch_chars++] = '\\';
mblen_str[1] = '\0';
***************
*** 2363,2368 ****
--- 2375,2394 ----
}
/* OK to fetch a character */
+ if ((!cstate->csv_mode || !first_char_in_line)
+ && !cstate->encoding_embeds_ascii
+ && (raw_buf_ptr + 4 <= copy_buf_len))
+ {
+
+ char *next = strpbrk(©_raw_buf[raw_buf_ptr], search_chars);
+
+ if (next != NULL)
+ {
+ raw_buf_ptr = next - copy_raw_buf;
+ first_char_in_line = false;
+ }
+ }
+
prev_raw_ptr = raw_buf_ptr;
c = copy_raw_buf[raw_buf_ptr++];
copy-script.sh
Description: application/shellscript
-- Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-patches
