Callgrind run

[Sebastian Gniazdowski <psprint@xxxxxxxxxxxx>]

Hello
I've run callgrind on Zsh, when executing syntax-highlighting code that
parses 823 lines of code:

2,269,560,047  ???:mb_metacharlenconv_r [/usr/local/bin/zsh-debug-opt]
1,698,947,505  ???:remnulargs [/usr/local/bin/zsh-debug-opt]
1,677,804,272  ???:_UTF8_mbrtowc [/usr/lib/system/libsystem_c.dylib]
1,425,973,736  ???:mbrtowc [/usr/lib/system/libsystem_c.dylib]
1,177,994,701  ???:untokenize [/usr/local/bin/zsh-debug-opt]
1,048,181,974  ???:mb_metacharlenconv [/usr/local/bin/zsh-debug-opt]
1,036,055,574  ???:getindex'2 [/usr/local/bin/zsh-debug-opt]
  793,202,632  ???:haswilds [/usr/local/bin/zsh-debug-opt]
  578,630,988  ???:mb_metastrlenend [/usr/local/bin/zsh-debug-opt]
  483,051,992  ???:szone_free_definite_size
  [/usr/lib/system/libsystem_malloc.dylib]
  436,411,797  ???:ztrsub [/usr/local/bin/zsh-debug-opt]
  364,444,476  ???:tiny_malloc_from_free_list
  [/usr/lib/system/libsystem_malloc.dylib]
  353,826,375  ???:pattrylen'2 [/usr/local/bin/zsh-debug-opt]
  280,090,072  ???:tiny_free_list_add_ptr
  [/usr/lib/system/libsystem_malloc.dylib]
  258,502,596  ???:strlen [/usr/lib/dyld]
  234,273,918  ???:pattrylen [/usr/local/bin/zsh-debug-opt]
  209,835,520  ???:szone_size [/usr/lib/system/libsystem_malloc.dylib]

To repeat the run clone
https://github.com/psprint/history-search-multi-word/ and add "valgrind
--tool=callgrind" before "zsh" (after exec) in parse.zsh, then run
./parse.zsh ./to-parse.zsh. I think this is a very good real world test.

Seems that Zsh execution could be greatly optimized if functions:
remnulargs, untokenize, haswilds could be optimized. Not sure if the
results are reasonable, as haswilds just iterates over a string and does
quite basic switch. The other two functions have nested loops, so they
look more likely as being time consuming. Maybe the nested loop can be
changed to something else?

Other pointed functions seem to be very valid / expected – multibyte
functions. They can be optimized if a courageous decision will be made –
to do what charnext / pattern.c does:

    if (!(patglobflags & GF_MULTIBYTE) || !(STOUC(*x) & 0x80))
        return x + 1;

I.e. to optimize for ASCII as subset of UTF-8 also when calling
MB_METACHARLEN, not only for MB_METASTRLEN (recent change).

-- 
  Sebastian Gniazdowski
  psprint@xxxxxxxxxxxx

--------------------------------------------------------------------------------
Profile data file 'callgrind.out.11879' (creator: callgrind-3.12.0)
--------------------------------------------------------------------------------
I1 cache: 
D1 cache: 
LL cache: 
Timerange: Basic block 0 - 2995164135
Trigger: Program termination
Profiled target:  zsh-debug-opt -f -c source "./testparse.zsh" "./to-parse.zsh" "changes.out" "" (PID 11879, part 1)
Events recorded:  Ir
Events shown:     Ir
Event sort order: Ir
Thresholds:       99
Include dirs:     
User annotated:   
Auto-annotation:  off

--------------------------------------------------------------------------------
            Ir 
--------------------------------------------------------------------------------
16,735,388,538  PROGRAM TOTALS

--------------------------------------------------------------------------------
           Ir  file:function
--------------------------------------------------------------------------------
2,269,560,047  ???:mb_metacharlenconv_r [/usr/local/bin/zsh-debug-opt]
1,698,947,505  ???:remnulargs [/usr/local/bin/zsh-debug-opt]
1,677,804,272  ???:_UTF8_mbrtowc [/usr/lib/system/libsystem_c.dylib]
1,425,973,736  ???:mbrtowc [/usr/lib/system/libsystem_c.dylib]
1,177,994,701  ???:untokenize [/usr/local/bin/zsh-debug-opt]
1,048,181,974  ???:mb_metacharlenconv [/usr/local/bin/zsh-debug-opt]
1,036,055,574  ???:getindex'2 [/usr/local/bin/zsh-debug-opt]
  793,202,632  ???:haswilds [/usr/local/bin/zsh-debug-opt]
  578,630,988  ???:mb_metastrlenend [/usr/local/bin/zsh-debug-opt]
  483,051,992  ???:szone_free_definite_size [/usr/lib/system/libsystem_malloc.dylib]
  436,411,797  ???:ztrsub [/usr/local/bin/zsh-debug-opt]
  364,444,476  ???:tiny_malloc_from_free_list [/usr/lib/system/libsystem_malloc.dylib]
  353,826,375  ???:pattrylen'2 [/usr/local/bin/zsh-debug-opt]
  280,090,072  ???:tiny_free_list_add_ptr [/usr/lib/system/libsystem_malloc.dylib]
  258,502,596  ???:strlen [/usr/lib/dyld]
  234,273,918  ???:pattrylen [/usr/local/bin/zsh-debug-opt]
  209,835,520  ???:szone_size [/usr/lib/system/libsystem_malloc.dylib]
  193,985,837  ???:tiny_free_list_remove_ptr [/usr/lib/system/libsystem_malloc.dylib]
  169,580,182  ???:szone_malloc_should_clear [/usr/lib/system/libsystem_malloc.dylib]
  143,109,122  ???:_platform_memmove$VARIANT$Nehalem [/usr/lib/system/libsystem_platform.dylib]
   97,432,800  ???:free [/usr/lib/dyld]
   97,335,179  ???:itype_end [/usr/local/bin/zsh-debug-opt]
   95,353,820  ???:get_tiny_free_size [/usr/lib/system/libsystem_malloc.dylib]
   83,934,500  ???:pthread_getspecific [/usr/lib/system/libsystem_pthread.dylib]
   81,015,036  ???:filesub [/usr/local/bin/zsh-debug-opt]
   68,738,845  ???:__strcpy_chk [/usr/lib/system/libsystem_c.dylib]
   60,927,832  ???:malloc_zone_malloc [/usr/lib/system/libsystem_malloc.dylib]
   57,698,352  ???:zalloc [/usr/local/bin/zsh-debug-opt]
   55,196,289  ???:bin_log [/usr/local/bin/zsh-debug-opt]
   54,517,015  ???:stpcpy [/usr/lib/system/libsystem_c.dylib]
   51,545,105  ???:setarrvalue [/usr/local/bin/zsh-debug-opt]
   49,052,650  ???:get_tiny_previous_free_msize [/usr/lib/system/libsystem_malloc.dylib]
   48,122,314  ???:ztrdup [/usr/local/bin/zsh-debug-opt]
   45,371,076  ???:mathevalarg'2 [/usr/local/bin/zsh-debug-opt]
   44,923,221  ???:arrlen [/usr/local/bin/zsh-debug-opt]
   44,888,769  ???:__vsnprintf_chk [/usr/lib/system/libsystem_c.dylib]
   43,521,301  ???:malloc [/usr/lib/dyld]
   33,548,312  ???:__chk_overlap [/usr/lib/system/libsystem_c.dylib]
   33,378,378  ???:execlist'2 [/usr/local/bin/zsh-debug-opt]
   32,027,315  ???:_platform_memset$VARIANT$Merom [/usr/lib/system/libsystem_platform.dylib]
   29,584,698  ???:_platform_strchr$VARIANT$Generic [/usr/lib/system/libsystem_platform.dylib]
   28,786,904  ???:hasher [/usr/local/bin/zsh-debug-opt]
   25,459,319  ???:zhalloc [/usr/local/bin/zsh-debug-opt]
   25,436,057  ???:modify [/usr/local/bin/zsh-debug-opt]
   23,233,085  ???:patcompile'2 [/usr/local/bin/zsh-debug-opt]
   23,114,835  ???:zsfree [/usr/local/bin/zsh-debug-opt]
   21,720,915  ???:_os_lock_spin_lock [/usr/lib/system/libsystem_platform.dylib]
   21,033,364  ???:execrestore'2 [/usr/local/bin/zsh-debug-opt]
   21,029,416  ???:ingetc [/usr/local/bin/zsh-debug-opt]
   20,619,575  ???:freearray [/usr/local/bin/zsh-debug-opt]
   18,246,076  ???:fetchvalue [/usr/local/bin/zsh-debug-opt]
   17,288,068  ???:isascii [/usr/lib/system/libsystem_c.dylib]
   16,274,888  ???:filesub'2 [/usr/local/bin/zsh-debug-opt]
   15,162,279  ???:haswilds'2 [/usr/local/bin/zsh-debug-opt]
   12,590,562  ???:parsestrnoerr [/usr/local/bin/zsh-debug-opt]
   10,881,530  ???:szone_malloc [/usr/lib/system/libsystem_malloc.dylib]
   10,206,971  ???:zstrtol_underscore [/usr/local/bin/zsh-debug-opt]
    9,997,508  ???:_pthread_mutex_unlock_slow [/usr/lib/system/libsystem_pthread.dylib]
    9,639,468  ???:_platform_strcmp [/usr/lib/system/libsystem_platform.dylib]
    9,404,226  ???:modify'2 [/usr/local/bin/zsh-debug-opt]
    8,688,566  ???:os_lock_unlock [/usr/lib/system/libsystem_platform.dylib]
    8,688,566  ???:os_lock_lock [/usr/lib/system/libsystem_platform.dylib]
    8,688,366  ???:_os_lock_spin_unlock [/usr/lib/system/libsystem_platform.dylib]
    8,497,692  ???:op [/usr/local/bin/zsh-debug-opt]
    8,390,890  ???:prefork [/usr/local/bin/zsh-debug-opt]
    8,223,809  ???:patcompstart [/usr/local/bin/zsh-debug-opt]
    7,962,974  ???:gethashnode2 [/usr/local/bin/zsh-debug-opt]
    7,766,705  ???:scanmatchtable [/usr/local/bin/zsh-debug-opt]
    7,013,693  ???:parsestrnoerr'2 [/usr/local/bin/zsh-debug-opt]
    6,917,568  ???:op'2 [/usr/local/bin/zsh-debug-opt]
    6,909,521  ???:getindex [/usr/local/bin/zsh-debug-opt]
    6,827,173  ???:_pthread_mutex_lock_slow [/usr/lib/system/libsystem_pthread.dylib]
    6,691,178  ???:hasbraces [/usr/local/bin/zsh-debug-opt]
    6,601,957  ???:mathevalarg [/usr/local/bin/zsh-debug-opt]
    6,523,091  ???:get_node_from_uniquing_table [/usr/lib/system/libsystem_malloc.dylib]
    6,465,840  ???:ecgetstr [/usr/local/bin/zsh-debug-opt]
    6,193,899  ???:getstrvalue [/usr/local/bin/zsh-debug-opt]
    6,178,975  ???:matheval'2 [/usr/local/bin/zsh-debug-opt]
    6,012,923  ???:patcompile [/usr/local/bin/zsh-debug-opt]
    5,721,631  ???:ImageLoaderMachOCompressed::trieWalk(unsigned char const*, unsigned char const*, char const*) [/usr/lib/dyld]
    5,083,953  ???:add [/usr/local/bin/zsh-debug-opt]
    4,864,901  ???:__vsnprintf_chk'2 [/usr/lib/system/libsystem_c.dylib]
    4,728,297  ???:dupstring [/usr/local/bin/zsh-debug-opt]
    4,331,738  ???:fetchvalue'2 [/usr/local/bin/zsh-debug-opt]
    4,212,315  ???:newparamtable [/usr/local/bin/zsh-debug-opt]
    4,034,794  ???:__vfprintf [/usr/lib/system/libsystem_c.dylib]
    3,977,804  ???:pattryrefs [/usr/local/bin/zsh-debug-opt]
    3,604,588  ???:assignstrvalue [/usr/local/bin/zsh-debug-opt]
    3,520,423  ???:matheval [/usr/local/bin/zsh-debug-opt]
    3,518,560  ???:mb_charinit [/usr/local/bin/zsh-debug-opt]