* Re: [PATCH] zrealloc on array+=( )
@ 2017-03-04 13:47 Sebastian Gniazdowski
2017-03-04 17:22 ` Bart Schaefer
0 siblings, 1 reply; 3+ messages in thread
From: Sebastian Gniazdowski @ 2017-03-04 13:47 UTC (permalink / raw)
To: zsh-workers
[-- Attachment #1: Type: text/plain, Size: 793 bytes --]
Hello,
I revisited the patch, tested with debug prints, added test cases that
stress things out. No code changes.
Thought to test how Bash (3.2) performs on appends:
# fun() { local -a arr; i=5001; while (( -- i )); do arr+=( "The
appended test string of medium length" ); done; }
# time fun
real 0m0.221s
user 0m0.214s
sys 0m0.004s
So it's 200 ms. The same test with no-zrealloc-Zsh is 2.94 s. With the
patch it's 116 ms (using time tool, typeset -F SECONDS reveals it's 4
ms). So this can be a motivation to apply the patch. We can leverage the
fact that operating system has size of the array and can extend it, and
this way beat Bash. Of course, the real deal here is to be able to do
data processing, e.g. log gathering, etc.
--
Sebastian Gniazdowski
psprint3@fastmail.com
[-- Attachment #2: array_zrealloc2.diff --]
[-- Type: text/plain, Size: 4240 bytes --]
diff --git a/Src/params.c b/Src/params.c
index 19cbb1c..8942fef 100644
--- a/Src/params.c
+++ b/Src/params.c
@@ -2723,24 +2723,57 @@ setarrvalue(Value v, char **val)
*p++ = *r++;
}
} else {
- p = new = (char **) zalloc(sizeof(char *)
- * (post_assignment_length + 1));
-
- for (i = 0; i < v->start; i++)
- *p++ = i < pre_assignment_length ? ztrdup(*q++) : ztrdup("");
- for (r = val; *r;) {
- /* Give away ownership of the string */
- *p++ = *r++;
- }
- if (v->end < pre_assignment_length)
- for (q = old + v->end; *q;)
- *p++ = ztrdup(*q++);
- *p = NULL;
+ /* arr+=( ... )
+ * arr[${#arr}+x,...]=( ... ) */
+ if (post_assignment_length > pre_assignment_length &&
+ pre_assignment_length <= v->start &&
+ pre_assignment_length > 0 &&
+ v->pm->gsu.a->setfn == arrsetfn)
+ {
+ p = new = (char **) zrealloc(old, sizeof(char *)
+ * (post_assignment_length + 1));
+
+ p += pre_assignment_length; /* after old elements */
+
+ /* Consider 1 < 0, case for a=( 1 ); a[1,..] =
+ * 1 < 1, case for a=( 1 ); a[2,..] = */
+ if (pre_assignment_length < v->start) {
+ for (i = pre_assignment_length; i < v->start; i++) {
+ *p++ = ztrdup("");
+ }
+ }
+
+ for (r = val; *r;) {
+ /* Give away ownership of the string */
+ *p++ = *r++;
+ }
+
+ /* v->end doesn't matter:
+ * a=( 1 2 ); a[4,100]=( a b ); echo "${(q@)a}"
+ * 1 2 '' a b */
+ *p = NULL;
+
+ v->pm->u.arr = NULL;
+ v->pm->gsu.a->setfn(v->pm, new);
+ } else {
+ p = new = (char **) zalloc(sizeof(char *)
+ * (post_assignment_length + 1));
+ for (i = 0; i < v->start; i++)
+ *p++ = i < pre_assignment_length ? ztrdup(*q++) : ztrdup("");
+ for (r = val; *r;) {
+ /* Give away ownership of the string */
+ *p++ = *r++;
+ }
+ if (v->end < pre_assignment_length)
+ for (q = old + v->end; *q;)
+ *p++ = ztrdup(*q++);
+ *p = NULL;
+
+ v->pm->gsu.a->setfn(v->pm, new);
+ }
DPUTS2(p - new != post_assignment_length, "setarrvalue: wrong allocation: %d 1= %lu",
post_assignment_length, (unsigned long)(p - new));
-
- v->pm->gsu.a->setfn(v->pm, new);
}
/* Ownership of all strings has been
diff --git a/Test/A06assign.ztst b/Test/A06assign.ztst
index bf39aee..fd2b417 100644
--- a/Test/A06assign.ztst
+++ b/Test/A06assign.ztst
@@ -133,6 +133,72 @@
>1 2 42 43 44 5
>1 2 42 100 99 5
+# (subsection: append to array)
+
+ array=( )
+ array[5,6]=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append to empty array by range
+>1 2 3
+>'' '' '' '' 1 2 3
+
+ array=( a )
+ array[5,6]=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append to 1-element array by range
+>a 1 2 3
+>a '' '' '' 1 2 3
+
+ array=( a b )
+ array[5,6]=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append to 2-element array by range
+>a b 1 2 3
+>a b '' '' 1 2 3
+
+ array=( a b )
+ array[5,5]=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append to 2-element array by [a,a] range
+>a b 1 2 3
+>a b '' '' 1 2 3
+
+ array=( a b c d )
+ array[5,6]=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append array by range, continuously
+>a b c d 1 2 3
+>a b c d 1 2 3
+
+ array=( a b c d )
+ array[5,5]=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append array by [a,a] range, continuously
+>a b c d 1 2 3
+>a b c d 1 2 3
+
+ array=( )
+ array+=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append empty array via +=
+>1 2 3
+>1 2 3
+
+ array=( a )
+ array+=( 1 2 3 )
+ print $array
+ print "${(q@)array}"
+0:Append 1-element array via +=
+>a 1 2 3
+>a 1 2 3
+
# tests of var+=scalar
s+=foo
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] zrealloc on array+=( )
2017-03-04 13:47 [PATCH] zrealloc on array+=( ) Sebastian Gniazdowski
@ 2017-03-04 17:22 ` Bart Schaefer
0 siblings, 0 replies; 3+ messages in thread
From: Bart Schaefer @ 2017-03-04 17:22 UTC (permalink / raw)
To: zsh-workers
On Mar 4, 5:47am, Sebastian Gniazdowski wrote:
}
} I revisited the patch, tested with debug prints, added test cases that
} stress things out. No code changes.
For the record, this looks fine, I don't see any reason not to pick
it up.
} We can leverage the fact that operating system has size of the array
} and can extend it, and this way beat Bash.
IIRC bash implements arrays sparsely as linked lists, so is going to
differ entirely from zsh in memory-use/execution-speed profile for
various array operations. "Beating" bash on some specific usage is
not especially meaningful.
} Of course, the real deal here is to be able to do
} data processing, e.g. log gathering, etc.
Which is not really what shells are intended to be used for ...
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] zrealloc on array+=( )
@ 2017-02-26 12:06 Sebastian Gniazdowski
0 siblings, 0 replies; 3+ messages in thread
From: Sebastian Gniazdowski @ 2017-02-26 12:06 UTC (permalink / raw)
To: zsh-workers
[-- Attachment #1: Type: text/plain, Size: 696 bytes --]
Hello,
optimization that finally targets much common use case and can sometimes
lead to faster Zsh startup.
fun() {
local -a arr
repeat 1000; arr+=( "The appended test string of medium length" );
}
local -F SECONDS=0; fun; echo $SECONDS
100 milliseconds vs 4 milliseconds. Just 1000 repetitions. For 5000, it
is 2.2 seconds vs 4 milliseconds.
I aggregate logs during startup, but didn't get gain as I forgot that I
aggregate as strings (~1000 $'\n' entries). Other tests shown that this
is best aggregation available – strings. So I'm in luck. But now there
could be superior and expected array aggregation.
--
Sebastian Gniazdowski
psprint2@fastmail.com
[-- Attachment #2: array_zrealloc.diff --]
[-- Type: text/plain, Size: 2907 bytes --]
diff --git a/Src/params.c b/Src/params.c
index 19cbb1c..2af24b5 100644
--- a/Src/params.c
+++ b/Src/params.c
@@ -2723,24 +2723,58 @@ setarrvalue(Value v, char **val)
*p++ = *r++;
}
} else {
- p = new = (char **) zalloc(sizeof(char *)
- * (post_assignment_length + 1));
-
- for (i = 0; i < v->start; i++)
- *p++ = i < pre_assignment_length ? ztrdup(*q++) : ztrdup("");
- for (r = val; *r;) {
- /* Give away ownership of the string */
- *p++ = *r++;
- }
- if (v->end < pre_assignment_length)
- for (q = old + v->end; *q;)
- *p++ = ztrdup(*q++);
- *p = NULL;
+ /* arr+=( ... )
+ * arr[${#arr}+x,...] = */
+ if (post_assignment_length > pre_assignment_length &&
+ pre_assignment_length <= v->start &&
+ pre_assignment_length > 0 &&
+ v->pm->gsu.a->setfn == arrsetfn)
+ {
+ p = new = (char **) zrealloc(old, sizeof(char *)
+ * (post_assignment_length + 1));
+
+ p += pre_assignment_length; /* after old elements */
+
+ /* Consider 1 < 0, case for a=( 1 ); a[1,..] =
+ * 1 < 1, case for a=( 1 ); a[2,..] = */
+ if (pre_assignment_length < v->start) {
+ /* Above <= implies we should run for i < v->start */
+ for (i = pre_assignment_length; i < v->start; i++) {
+ *p++ = ztrdup("");
+ }
+ }
+
+ for (r = val; *r;) {
+ /* Give away ownership of the string */
+ *p++ = *r++;
+ }
+
+ /* v->end doesn't matter:
+ * a=( 1 2 ); a[4,100]=( a b ); echo "${(q@)a}"
+ * 1 2 '' a b */
+ *p = NULL;
+
+ v->pm->u.arr = NULL;
+ v->pm->gsu.a->setfn(v->pm, new);
+ } else {
+ p = new = (char **) zalloc(sizeof(char *)
+ * (post_assignment_length + 1));
+ for (i = 0; i < v->start; i++)
+ *p++ = i < pre_assignment_length ? ztrdup(*q++) : ztrdup("");
+ for (r = val; *r;) {
+ /* Give away ownership of the string */
+ *p++ = *r++;
+ }
+ if (v->end < pre_assignment_length)
+ for (q = old + v->end; *q;)
+ *p++ = ztrdup(*q++);
+ *p = NULL;
+
+ v->pm->gsu.a->setfn(v->pm, new);
+ }
DPUTS2(p - new != post_assignment_length, "setarrvalue: wrong allocation: %d 1= %lu",
post_assignment_length, (unsigned long)(p - new));
-
- v->pm->gsu.a->setfn(v->pm, new);
}
/* Ownership of all strings has been
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2017-03-04 17:29 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-03-04 13:47 [PATCH] zrealloc on array+=( ) Sebastian Gniazdowski
2017-03-04 17:22 ` Bart Schaefer
-- strict thread matches above, loose matches on Subject: below --
2017-02-26 12:06 Sebastian Gniazdowski
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/zsh/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).