To: vim_dev@googlegroups.com
Subject: Patch 7.3.434
Fcc: outbox
From: Bram Moolenaar <Bram@moolenaar.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
------------
 
Patch 7.3.434
Problem:    Using join() can be slow.
Solution:   Compute the size of the result before allocation to avoid a lot of
            allocations and copies. (Taro Muraoka)
Files:      src/eval.c
 
 
*** ../vim-7.3.433/src/eval.c	2012-02-05 00:39:14.000000000 +0100
--- src/eval.c	2012-02-06 00:05:31.000000000 +0100
***************
*** 442,447 ****
--- 442,448 ----
  static list_T *list_copy __ARGS((list_T *orig, int deep, int copyID));
  static void list_remove __ARGS((list_T *l, listitem_T *item, listitem_T *item2));
  static char_u *list2string __ARGS((typval_T *tv, int copyID));
+ static int list_join_inner __ARGS((garray_T *gap, list_T *l, char_u *sep, int echo_style, int copyID, garray_T *join_gap));
  static int list_join __ARGS((garray_T *gap, list_T *l, char_u *sep, int echo, int copyID));
  static int free_unref_items __ARGS((int copyID));
  static void set_ref_in_ht __ARGS((hashtab_T *ht, int copyID));
***************
*** 6571,6617 ****
      return (char_u *)ga.ga_data;
  }
  
! /*
!  * Join list "l" into a string in "*gap", using separator "sep".
!  * When "echo_style" is TRUE use String as echoed, otherwise as inside a List.
!  * Return FAIL or OK.
!  */
      static int
! list_join(gap, l, sep, echo_style, copyID)
!     garray_T	*gap;
      list_T	*l;
      char_u	*sep;
      int		echo_style;
      int		copyID;
  {
      int		first = TRUE;
      char_u	*tofree;
      char_u	numbuf[NUMBUFLEN];
      listitem_T	*item;
      char_u	*s;
  
      for (item = l->lv_first; item != NULL && !got_int; item = item->li_next)
      {
- 	if (first)
- 	    first = FALSE;
- 	else
- 	    ga_concat(gap, sep);
- 
  	if (echo_style)
  	    s = echo_string(&item->li_tv, &tofree, numbuf, copyID);
  	else
  	    s = tv2string(&item->li_tv, &tofree, numbuf, copyID);
- 	if (s != NULL)
- 	    ga_concat(gap, s);
- 	vim_free(tofree);
  	if (s == NULL)
  	    return FAIL;
  	line_breakcheck();
      }
      return OK;
  }
  
  /*
   * Garbage collection for lists and dictionaries.
   *
   * We use reference counts to be able to free most items right away when they
--- 6572,6690 ----
      return (char_u *)ga.ga_data;
  }
  
! typedef struct join_S {
!     char_u	*s;
!     char_u	*tofree;
! } join_T;
! 
      static int
! list_join_inner(gap, l, sep, echo_style, copyID, join_gap)
!     garray_T	*gap;		/* to store the result in */
      list_T	*l;
      char_u	*sep;
      int		echo_style;
      int		copyID;
+     garray_T	*join_gap;	/* to keep each list item string */
  {
+     int		i;
+     join_T	*p;
+     int		len;
+     int		sumlen = 0;
      int		first = TRUE;
      char_u	*tofree;
      char_u	numbuf[NUMBUFLEN];
      listitem_T	*item;
      char_u	*s;
  
+     /* Stringify each item in the list. */
      for (item = l->lv_first; item != NULL && !got_int; item = item->li_next)
      {
  	if (echo_style)
  	    s = echo_string(&item->li_tv, &tofree, numbuf, copyID);
  	else
  	    s = tv2string(&item->li_tv, &tofree, numbuf, copyID);
  	if (s == NULL)
  	    return FAIL;
+ 
+ 	len = (int)STRLEN(s);
+ 	sumlen += len;
+ 
+ 	ga_grow(join_gap, 1);
+ 	p = ((join_T *)join_gap->ga_data) + (join_gap->ga_len++);
+ 	if (tofree != NULL || s != numbuf)
+ 	{
+ 	    p->s = s;
+ 	    p->tofree = tofree;
+ 	}
+ 	else
+ 	{
+ 	    p->s = vim_strnsave(s, len);
+ 	    p->tofree = p->s;
+ 	}
+ 
+ 	line_breakcheck();
+     }
+ 
+     /* Allocate result buffer with its total size, avoid re-allocation and
+      * multiple copy operations.  Add 2 for a tailing ']' and NUL. */
+     if (join_gap->ga_len >= 2)
+ 	sumlen += (int)STRLEN(sep) * (join_gap->ga_len - 1);
+     if (ga_grow(gap, sumlen + 2) == FAIL)
+ 	return FAIL;
+ 
+     for (i = 0; i < join_gap->ga_len && !got_int; ++i)
+     {
+ 	if (first)
+ 	    first = FALSE;
+ 	else
+ 	    ga_concat(gap, sep);
+ 	p = ((join_T *)join_gap->ga_data) + i;
+ 
+ 	if (p->s != NULL)
+ 	    ga_concat(gap, p->s);
  	line_breakcheck();
      }
+ 
      return OK;
  }
  
  /*
+  * Join list "l" into a string in "*gap", using separator "sep".
+  * When "echo_style" is TRUE use String as echoed, otherwise as inside a List.
+  * Return FAIL or OK.
+  */
+     static int
+ list_join(gap, l, sep, echo_style, copyID)
+     garray_T	*gap;
+     list_T	*l;
+     char_u	*sep;
+     int		echo_style;
+     int		copyID;
+ {
+     garray_T	join_ga;
+     int		retval;
+     join_T	*p;
+     int		i;
+ 
+     ga_init2(&join_ga, (int)sizeof(join_T), l->lv_len);
+     retval = list_join_inner(gap, l, sep, echo_style, copyID, &join_ga);
+ 
+     /* Dispose each item in join_ga. */
+     if (join_ga.ga_data != NULL)
+     {
+ 	p = (join_T *)join_ga.ga_data;
+ 	for (i = 0; i < join_ga.ga_len; ++i)
+ 	{
+ 	    vim_free(p->tofree);
+ 	    ++p;
+ 	}
+ 	ga_clear(&join_ga);
+     }
+ 
+     return retval;
+ }
+ 
+ /*
   * Garbage collection for lists and dictionaries.
   *
   * We use reference counts to be able to free most items right away when they
***************
*** 13406,13412 ****
      char_u	*rhs;
      int		mode;
      int		abbr = FALSE;
!     int         get_dict = FALSE;
      mapblock_T	*mp;
      int		buffer_local;
  
--- 13479,13485 ----
      char_u	*rhs;
      int		mode;
      int		abbr = FALSE;
!     int		get_dict = FALSE;
      mapblock_T	*mp;
      int		buffer_local;
  
*** ../vim-7.3.433/src/version.c	2012-02-05 23:10:25.000000000 +0100
--- src/version.c	2012-02-06 00:10:23.000000000 +0100
***************
*** 716,717 ****
--- 716,719 ----
  {   /* Add new patch number below this line */
+ /**/
+     434,
  /**/
 
-- 
hundred-and-one symptoms of being an internet addict:
30. Even though you died last week, you've managed to retain OPS on your
    favorite IRC channel.
 
 /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net   \\\
///        sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\  an exciting new programming language -- http://www.Zimbu.org        ///
 \\\            help me help AIDS victims -- http://ICCF-Holland.org    ///