From: Sebastian Gniazdowski <psprint3@fastmail.com>
To: zsh-workers@zsh.org
Subject: Status of optimizations – can have native buffers
Date: Sat, 04 Mar 2017 05:49:54 -0800 [thread overview]
Message-ID: <1488635394.1730469.900258024.2D9CA43E@webmail.messagingengine.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1423 bytes --]
Hello,
with the optimizations for array (Zsh 5.3.1-dev-0):
typeset -a array
array[100]=""
array[20,29]=( 1 2 3 4 5 6 7 8 9 10 )
we can now have somewhat "native" buffers in zsh. Above will not do
anything with elements outside <20,30> range.
One use case are 2-dimensional arrays, with e.g. the library I sent to
zsh-users (ID: 21926). Created are e.g. 10 fixed rows of 100 elements.
Then it's possible to fill rows by storing to computed indexes. Or to
fill entire row by storing to <row_begin,row_end>.
The same has been done with strings (Zsh 5.3), and string can be a
native buffer too.
That said, when I test with my screen-saver zsh-morpho
(https://github.com/psprint/zsh-morpho), which uses hash tables for its
pixel native buffer, arrays are still slower. It is 55.9 s vs. 27.3 s.
Callgrind reveals the cause:
59,930,247,427 arrlen_le [/usr/local/bin/zsh-5.3.1-dev-0_O2]
15,675,075,695 szone_free_definite_size
[/usr/lib/system/libsystem_malloc.dylib]
11,983,363,082 tiny_malloc_from_free_list
[/usr/lib/system/libsystem_malloc.dylib]
8,037,180,402 tiny_free_list_add_ptr
[/usr/lib/system/libsystem_malloc.dylib]
7,181,545,835 _platform_memmove$VARIANT$Nehalem
[/usr/lib/system/libsystem_platform.dylib]
(full data in attachement)
The buffer has size 34x158=5372 elements. Without the optimizations that
are the topic, time is 367 s.
--
Sebastian Gniazdowski
psprint3@fastmail.com
[-- Attachment #2: callgrind_annotate.txt --]
[-- Type: text/plain, Size: 9089 bytes --]
--------------------------------------------------------------------------------
Profile data file 'callgrind.out.9896' (creator: callgrind-3.12.0)
--------------------------------------------------------------------------------
I1 cache:
D1 cache:
LL cache:
Timerange: Basic block 0 - 44213777818
Trigger: Program termination
Profiled target: zsh-5.3.1-dev-0_O2 ./zmorpho (PID 9896, part 1)
Events recorded: Ir
Events shown: Ir
Event sort order: Ir
Thresholds: 99
Include dirs:
User annotated:
Auto-annotation: off
--------------------------------------------------------------------------------
Ir
--------------------------------------------------------------------------------
210,464,472,644 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir file:function
--------------------------------------------------------------------------------
59,930,247,427 ???:arrlen_le [/usr/local/bin/zsh-5.3.1-dev-0_O2]
15,675,075,695 ???:szone_free_definite_size [/usr/lib/system/libsystem_malloc.dylib]
11,983,363,082 ???:tiny_malloc_from_free_list [/usr/lib/system/libsystem_malloc.dylib]
8,037,180,402 ???:tiny_free_list_add_ptr [/usr/lib/system/libsystem_malloc.dylib]
7,181,545,835 ???:_platform_memmove$VARIANT$Nehalem [/usr/lib/system/libsystem_platform.dylib]
6,887,423,013 ???:szone_size [/usr/lib/system/libsystem_malloc.dylib]
6,701,641,389 ???:itype_end [/usr/local/bin/zsh-5.3.1-dev-0_O2]
6,668,004,434 ???:arrlen [/usr/local/bin/zsh-5.3.1-dev-0_O2]
5,979,575,631 ???:tiny_free_list_remove_ptr [/usr/lib/system/libsystem_malloc.dylib]
5,583,741,132 ???:szone_malloc_should_clear [/usr/lib/system/libsystem_malloc.dylib]
3,676,908,734 ???:strcpy [/usr/lib/dyld]
3,229,526,238 ???:free [/usr/lib/dyld]
3,006,353,708 ???:get_tiny_free_size [/usr/lib/system/libsystem_malloc.dylib]
2,690,849,561 ???:strlen [/usr/lib/dyld]
2,677,510,801 ???:stringsubst [/usr/local/bin/zsh-5.3.1-dev-0_O2]
2,558,606,524 ???:stringsubst'2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
2,370,009,449 ???:ingetc [/usr/local/bin/zsh-5.3.1-dev-0_O2]
2,103,253,219 ???:zalloc [/usr/local/bin/zsh-5.3.1-dev-0_O2]
2,010,130,192 ???:malloc_zone_malloc [/usr/lib/system/libsystem_malloc.dylib]
1,980,835,207 ???:strtod_l [/usr/lib/system/libsystem_c.dylib]
1,871,413,725 ???:dquote_parse [/usr/local/bin/zsh-5.3.1-dev-0_O2]
1,651,513,719 ???:zhalloc [/usr/local/bin/zsh-5.3.1-dev-0_O2]
1,641,875,732 ???:_platform_strcmp [/usr/lib/system/libsystem_platform.dylib]
1,604,082,741 ???:get_tiny_previous_free_msize [/usr/lib/system/libsystem_malloc.dylib]
1,574,144,473 ???:zzlex [/usr/local/bin/zsh-5.3.1-dev-0_O2]
1,435,808,720 ???:malloc [/usr/lib/dyld]
1,334,946,291 ???:ztrdup [/usr/local/bin/zsh-5.3.1-dev-0_O2]
1,255,063,534 ???:__quorem_D2A [/usr/lib/system/libsystem_c.dylib]
1,221,146,102 ???:__multadd_D2A [/usr/lib/system/libsystem_c.dylib]
1,165,383,862 ???:untokenize [/usr/local/bin/zsh-5.3.1-dev-0_O2]
1,098,371,849 ???:lexconstant [/usr/local/bin/zsh-5.3.1-dev-0_O2]
1,069,952,015 ???:fetchvalue [/usr/local/bin/zsh-5.3.1-dev-0_O2]
982,451,064 ???:remnulargs [/usr/local/bin/zsh-5.3.1-dev-0_O2]
965,483,295 ???:paramsubst [/usr/local/bin/zsh-5.3.1-dev-0_O2]
853,269,280 ???:getarg [/usr/local/bin/zsh-5.3.1-dev-0_O2]
792,779,000 ???:op [/usr/local/bin/zsh-5.3.1-dev-0_O2]
790,688,907 ???:hasher [/usr/local/bin/zsh-5.3.1-dev-0_O2]
771,110,306 ???:checkunary [/usr/local/bin/zsh-5.3.1-dev-0_O2]
763,084,062 ???:setlocale [/usr/lib/system/libsystem_c.dylib]
762,984,113 ???:setarrvalue [/usr/local/bin/zsh-5.3.1-dev-0_O2]
740,301,374 ???:mathparse'2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
717,789,930 ???:_os_lock_spin_lock [/usr/lib/system/libsystem_platform.dylib]
687,889,980 ???:__Balloc_D2A [/usr/lib/system/libsystem_c.dylib]
661,099,642 ???:__mult_D2A [/usr/lib/system/libsystem_c.dylib]
645,284,640 ???:paramsubst'2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
644,208,465 ???:__lshift_D2A [/usr/lib/system/libsystem_c.dylib]
628,587,537 ???:gethashnode2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
623,241,531 ???:addvars [/usr/local/bin/zsh-5.3.1-dev-0_O2]
595,811,848 ???:__dtoa [/usr/lib/system/libsystem_c.dylib]
585,980,177 ???:__Bfree_D2A [/usr/lib/system/libsystem_c.dylib]
585,163,299 ???:loadlocale [/usr/lib/system/libsystem_c.dylib]
582,166,785 ???:mathparse [/usr/local/bin/zsh-5.3.1-dev-0_O2]
478,719,744 ???:getparamnode [/usr/local/bin/zsh-5.3.1-dev-0_O2]
464,243,313 ???:mathevall [/usr/local/bin/zsh-5.3.1-dev-0_O2]
457,242,648 ???:add [/usr/local/bin/zsh-5.3.1-dev-0_O2]
444,824,636 ???:zsfree [/usr/local/bin/zsh-5.3.1-dev-0_O2]
438,807,694 ???:getindex [/usr/local/bin/zsh-5.3.1-dev-0_O2]
427,077,934 ???:__vfprintf [/usr/lib/system/libsystem_c.dylib]
418,216,827 ???:dupstring [/usr/local/bin/zsh-5.3.1-dev-0_O2]
406,725,998 ???:fetchvalue'2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
383,005,195 ???:zstrtol_underscore [/usr/local/bin/zsh-5.3.1-dev-0_O2]
380,580,653 ???:_platform_strchr$VARIANT$Generic [/usr/lib/system/libsystem_platform.dylib]
379,564,975 ???:__numeric_load_locale [/usr/lib/system/libsystem_c.dylib]
377,953,347 ???:inpoptop [/usr/local/bin/zsh-5.3.1-dev-0_O2]
358,951,860 ???:szone_malloc [/usr/lib/system/libsystem_malloc.dylib]
316,823,215 ???:__cmp_D2A [/usr/lib/system/libsystem_c.dylib]
305,846,720 ???:freearray [/usr/local/bin/zsh-5.3.1-dev-0_O2]
303,615,681 ???:hist_context_save [/usr/local/bin/zsh-5.3.1-dev-0_O2]
297,508,538 ???:watchlog_match [/usr/local/bin/zsh-5.3.1-dev-0_O2]
295,769,198 ???:__vsnprintf_chk [/usr/lib/system/libsystem_c.dylib]
287,116,172 ???:os_lock_unlock [/usr/lib/system/libsystem_platform.dylib]
287,116,172 ???:os_lock_lock [/usr/lib/system/libsystem_platform.dylib]
287,115,972 ???:_os_lock_spin_unlock [/usr/lib/system/libsystem_platform.dylib]
272,071,205 ???:hist_context_restore [/usr/local/bin/zsh-5.3.1-dev-0_O2]
268,128,151 ???:parse_context_restore [/usr/local/bin/zsh-5.3.1-dev-0_O2]
263,544,579 ???:execlist'2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
260,249,491 ???:hbegin [/usr/local/bin/zsh-5.3.1-dev-0_O2]
258,703,816 ???:__vsnprintf_chk'2 [/usr/lib/system/libsystem_c.dylib]
257,234,183 ???:_platform_bzero$VARIANT$Merom [/usr/lib/system/libsystem_platform.dylib]
245,441,859 ???:getmathparam [/usr/local/bin/zsh-5.3.1-dev-0_O2]
242,921,408 ???:prefork [/usr/local/bin/zsh-5.3.1-dev-0_O2]
240,386,850 ???:prefork'2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
237,246,060 ???:__s2b_D2A [/usr/lib/system/libsystem_c.dylib]
236,583,660 ???:parse_context_save [/usr/local/bin/zsh-5.3.1-dev-0_O2]
228,942,730 ???:__diff_D2A [/usr/lib/system/libsystem_c.dylib]
224,754,367 ???:inpush [/usr/local/bin/zsh-5.3.1-dev-0_O2]
221,552,781 ???:getstrvalue [/usr/local/bin/zsh-5.3.1-dev-0_O2]
215,349,190 ???:get_node_from_uniquing_table [/usr/lib/system/libsystem_malloc.dylib]
209,424,935 ???:convbase_ptr [/usr/local/bin/zsh-5.3.1-dev-0_O2]
203,022,100 ???:dupstrpfx [/usr/local/bin/zsh-5.3.1-dev-0_O2]
197,153,050 ???:lex_context_save [/usr/local/bin/zsh-5.3.1-dev-0_O2]
195,374,559 ???:strncpy [/usr/lib/dyld]
193,209,994 ???:zcontext_save_partial [/usr/local/bin/zsh-5.3.1-dev-0_O2]
190,469,954 ???:__d2b_D2A [/usr/lib/system/libsystem_c.dylib]
187,983,320 ???:getnumvalue [/usr/local/bin/zsh-5.3.1-dev-0_O2]
187,398,894 ???:arithsubst [/usr/local/bin/zsh-5.3.1-dev-0_O2]
185,323,872 ???:zcontext_restore_partial [/usr/local/bin/zsh-5.3.1-dev-0_O2]
181,385,636 ???:hend [/usr/local/bin/zsh-5.3.1-dev-0_O2]
181,170,554 ???:assignstrvalue [/usr/local/bin/zsh-5.3.1-dev-0_O2]
177,453,442 ???:inputsetline [/usr/local/bin/zsh-5.3.1-dev-0_O2]
176,710,920 ???:assignsparam [/usr/local/bin/zsh-5.3.1-dev-0_O2]
168,822,313 ???:ecgetstr [/usr/local/bin/zsh-5.3.1-dev-0_O2]
165,608,562 ???:lex_context_restore [/usr/local/bin/zsh-5.3.1-dev-0_O2]
165,164,992 ???:execsimple'2 [/usr/local/bin/zsh-5.3.1-dev-0_O2]
158,197,295 ???:__error [/usr/lib/system/libsystem_kernel.dylib]
155,692,436 ???:__sfvwrite [/usr/lib/system/libsystem_c.dylib]
154,124,892 ???:strcatsub [/usr/local/bin/zsh-5.3.1-dev-0_O2]
153,573,732 ???:__b2d_D2A [/usr/lib/system/libsystem_c.dylib]
141,574,370 ???:__pow5mult_D2A [/usr/lib/system/libsystem_c.dylib]
140,403,054 ???:parse_subscript [/usr/local/bin/zsh-5.3.1-dev-0_O2]
132,539,796 ???:zshlex_raw_add [/usr/local/bin/zsh-5.3.1-dev-0_O2]
131,809,956 ???:filesubstr [/usr/local/bin/zsh-5.3.1-dev-0_O2]
130,952,151 ???:filesub [/usr/local/bin/zsh-5.3.1-dev-0_O2]
130,475,899 ???:localeconv_l [/usr/lib/system/libsystem_c.dylib]
110,035,356 ???:pthread_getspecific [/usr/lib/system/libsystem_pthread.dylib]
106,487,955 ???:inungetc [/usr/local/bin/zsh-5.3.1-dev-0_O2]
94,891,375 ???:__detect_path_locale [/usr/lib/system/libsystem_c.dylib]
next reply other threads:[~2017-03-04 13:49 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-03-04 13:49 Sebastian Gniazdowski [this message]
2017-03-04 15:33 ` Sebastian Gniazdowski
2017-03-05 0:00 ` Status of optimiza tions - can have n ative buffers Bart Schaefer
2017-03-05 9:32 ` Sebastian Gniazdowski
2017-03-05 16:29 ` Bart Schaefer
2017-03-13 9:01 ` Status of optimizations – can have native buffers Sebastian Gniazdowski
2017-03-13 10:51 ` Sebastian Gniazdowski
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1488635394.1730469.900258024.2D9CA43E@webmail.messagingengine.com \
--to=psprint3@fastmail.com \
--cc=zsh-workers@zsh.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).