search

jcs-elpa / flx-rs

flx in Rust using dynamic module
GNU General Public License v3.0
22 stars 8 forks source link

flx-rs with high candidate count becomes slower for repeated calls to flx-score #3

Closed jojojames closed 2 years ago

jojojames commented 2 years ago

Using the configuration/completion-style defined here: https://github.com/lewang/flx/issues/54#issuecomment-1126858084

and then using a homegrown zsh-history completing-read function like this:

(defun zsh-history ()
  "Copy a command from ~/.zsh_history."
  (interactive)
  ;; https://emacs.stackexchange.com/questions/8115/make-completing-read-respect-sorting-order-of-a-collection
  (let* ((my-presorted-completion-table-fn
          (defun my-presorted-completion-table (completions)
            (lambda (string pred action)
              (if (eq action 'metadata)
                  `(metadata (display-sort-function . ,#'identity))
                (complete-with-action action completions string pred)))))
         (command
          (with-temp-buffer
            (insert-file-contents-literally "~/.zsh_history")
            (let ((history-list
                   (split-string (buffer-string)
                                 "^:[[:space:]][[:digit:]]+:0;"
                                 t
                                 "\n")))
              (completing-read
               "Command: "
               (reverse history-list)
               ;; (funcall my-presorted-completion-table-fn
               ;;          (reverse history-list))
               )))))
    (when command
      (message (format "Copying %s to clipboard." command))
      (kill-new command))))

If I log the time it takes for flx-rs-score to run, like so:

(measure-time
                                         (if (fboundp 'flx-rs-score)
                                             (flx-rs-score x string)
                                           (flx-score x string flx-strings-cache)))

Logs printed begins to look like this:

length list: 100
0.000015
0.000010
0.000015
0.000013
0.000019
0.000010 [2 times]
0.000013
0.000010
0.000014
0.000011
0.000021
0.000012
0.000011
0.000013
0.000010
0.000025
0.000014
0.000012
0.000013
0.000012 [3 times]
0.000010
0.000014
0.000011
0.000036
0.000014
0.000013
0.000011
0.000014
0.000015
0.000013
0.000019
0.000013
0.000022
0.000011
0.000022
0.000019
0.000016
0.000015
0.000020
0.000018
0.000015
0.000023
0.000019
0.000030
0.000021
0.000017
0.000016
0.000033 [2 times]
0.000025
0.000032
0.000037
0.000042
0.000075
0.000083
0.000102
0.000036
0.000103
0.000036
0.000062
0.000039
0.000233
0.001003
0.000277
0.000221 [2 times]
0.000224
0.000267
0.001036
0.001079
0.001040
0.001012
0.001023
0.001117
0.001192
0.001074
0.001176
0.001157
0.001135
0.001231
0.001189
0.339852
0.343824
0.345322
0.464961
0.478860
0.493561
0.509827
0.562074
0.496061
0.574823
0.577873
0.596355
0.579275
0.598657
0.592434

If I use the regular flx:

length list: 100
0.000019
0.000019
0.000009
0.000007
0.000006
0.000007
0.000006
0.000008
0.000007
0.000006
0.000011
0.000008
0.000007
0.000006
0.000007
0.000006
0.000007 [2 times]
0.000008
0.000013
0.000008
0.000006
0.000007 [2 times]
0.000008
0.000005
0.000007
0.000006
0.000007 [3 times]
0.000006
0.000008
0.000007
0.000006
0.000008
0.000007
0.000009
0.000008 [2 times]
0.000007
0.000009
0.000008
0.000009
0.000007
0.000008
0.000011
0.000009
0.000014
0.000010
0.000007 [2 times]
0.000008
0.000007
0.000008
0.000009
0.000008
0.000007
0.000017 [2 times]
0.000024
0.000007
0.000023
0.000008 [3 times]
0.000018
0.000150
0.000019
0.000017
0.000016
0.000018
0.000017
0.000047
0.000048
0.000046
0.000106
0.000046
0.000053
0.000050
0.000048
0.000047 [2 times]
0.000046
0.000051
0.000058
0.008030
0.008264
0.008223
0.010238
0.010192
0.010539
0.010813
0.012386
0.011142
0.013391
0.013276
0.012608
0.012992
0.011483
0.012428
0.196764
jcs090218 commented 2 years ago

I cannot produce this issue

(dotimes (x 1000)
  (measure-time
   (flx-rs-score "switch-to-buffer" "s-t-b")))

I got

0.000036  ; this is first log
...
0.000021  ; this is last log

I don't think the high candidate count would add up anything. My best guess is the flx-strings-cache cache. I haven't implement the cache variable since I don't really know how, and the speed is generally faster so I don't feel it's necessary to implement it.

jojojames commented 2 years ago

Got it, you're right. flx-rs-score is struggling to keep up with really long strings, e.g.

(measure-time
 (flx-rs-score "/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/clang -x objective-c -arch x86_64 -fmessage-length=0 -fdiagnostics-show-note-include-stack -fmacro-backtrace-limit=0 -std=c99 -fobjc-arc -fmodules -fmodules-cache-path=/Users/james/Library/Developer/Xcode/DerivedData/ModuleCache -fmodules-prune-interval=86400 -fmodules-prune-after=345600 -fbuild-session-file=/Users/james/Library/Developer/Xcode/DerivedData/ModuleCache/Session.modulevalidation -fmodules-validate-once-per-build-session -Wnon-modular-include-in-framework-module -Werror=non-modular-include-in-framework-module -Wno-trigraphs -fpascal-strings -O0 -Wno-missing-field-initializers -Wno-missing-prototypes -Wno-implicit-atomic-properties -Wno-arc-repeated-use-of-weak -Wno-missing-braces -Wparentheses -Wswitch -Wno-unused-function -Wno-unused-label -Wno-unused-parameter -Wunused-variable -Wunused-value -Wno-empty-body -Wno-uninitialized -Wno-unknown-pragmas -Wno-shadow -Wno-four-char-constants -Wno-conversion -Wno-constant-conversion -Wno-int-conversion -Wno-bool-conversion -Wno-enum-conversion -Wshorten-64-to-32 -Wpointer-sign -Wno-newline-eof -Wno-selector -Wno-strict-selector-match -Wno-undeclared-selector -Wno-deprecated-implementations -DCOCOAPODS=1 -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator9.3.sdk -fasm-blocks -fstrict-aliasing -Wprotocol -Wdeprecated-declarations -mios-simulator-version-min=7.0 -g -fvisibility=hidden -Wno-sign-conversion -fobjc-abi-version=2 -fobjc-legacy-dispatch -iquote /Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/Dummyapp-generated-files.hmap -I/Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/Dummyapp-own-target-headers.hmap -I/Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/Dummyapp-all-target-headers.hmap -iquote /Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/Dummyapp-project-headers.hmap -iquoteFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/simulator -iquote/Users/james/Developer/dummyappios/iOSTest/Frameworks/lib/iphoneos -I/Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Products/Debug-iphonesimulator/include -I/Users/james/Developer/dummyappios/iOSTest/Video/vpx -I/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator9.3.sdk/usr/include/libxml2 -I/Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public -I/Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/Google-Mobile-Ads-SDK -I/Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/RMUniversalAlert -I/Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/UIActionSheet+Blocks -I/Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/UIAlertController+Blocks -I/Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/UIAlertView+Blocks -I/Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/mopub-ios-sdk -IFrameworks/ThirdParty/common-ngn-stack -IFrameworks/ThirdParty/ios-ngn-stack -IFrameworks/ThirdParty/doubango/bindings/_common -IFrameworks/ThirdParty/doubango/tinySDP/include -IFrameworks/ThirdParty/doubango/tinySMS/include -IFrameworks/ThirdParty/doubango/tinyHTTP/include -IFrameworks/ThirdParty/doubango/tinySIP/include -I$DOUBANGO/HOME/tinyMSRP/include -IFrameworks/ThirdParty/doubango/tinyMEDIA/include -IFrameworks/ThirdParty/doubango/tinyNET/src -IFrameworks/ThirdParty/doubango/tinySAK/src -IFrameworks/ThirdParty/doubango/tinyDAV/include -IFrameworks/ThirdParty/doubango/tinyBFCP/include -IFrameworks -IFrameworks/lib -IFrameworks/MRVideoCall -IFrameworks/ThirdParty -IFrameworks/lib/iphoneos -IFrameworks/lib/iphonesimulator -IFrameworks/MRVideoCall/Assets -IFrameworks/ThirdParty/common-ngn-stack -IFrameworks/ThirdParty/doubango -IFrameworks/ThirdParty/ios-ngn-stack -IFrameworks/ThirdParty/Lumberjack -IFrameworks/MRVideoCall/Assets/Artwork -IFrameworks/MRVideoCall/Assets/Classes -IFrameworks/ThirdParty/common-ngn-stack/events -IFrameworks/ThirdParty/common-ngn-stack/media -IFrameworks/ThirdParty/common-ngn-stack/model -IFrameworks/ThirdParty/common-ngn-stack/services -IFrameworks/ThirdParty/common-ngn-stack/sip -IFrameworks/ThirdParty/common-ngn-stack/sound -IFrameworks/ThirdParty/common-ngn-stack/storage -IFrameworks/ThirdParty/common-ngn-stack/utils -IFrameworks/ThirdParty/doubango/android-projects -IFrameworks/ThirdParty/doubango/android-utils -IFrameworks/ThirdParty/doubango/bindings -IFrameworks/ThirdParty/doubango/documentation -IFrameworks/ThirdParty/doubango/dtmf -IFrameworks/ThirdParty/doubango/g729a -IFrameworks/ThirdParty/doubango/g729b -IFrameworks/ThirdParty/doubango/images -IFrameworks/ThirdParty/doubango/plugins -IFrameworks/ThirdParty/doubango/rtpdump -IFrameworks/ThirdParty/doubango/Samples -IFrameworks/ThirdParty/doubango/schemas -IFrameworks/ThirdParty/doubango/thirdparties -IFrameworks/ThirdParty/doubango/tinyBFCP -IFrameworks/ThirdParty/doubango/tinyDAV -IFrameworks/ThirdParty/doubango/tinyDEMO -IFrameworks/ThirdParty/doubango/tinyHTTP -IFrameworks/ThirdParty/doubango/tinyIPSec -IFrameworks/ThirdParty/doubango/tinyMEDIA -IFrameworks/ThirdParty/doubango/tinyMSRP -IFrameworks/ThirdParty/doubango/tinyNET -IFrameworks/ThirdParty/doubango/tinyROHC -IFrameworks/ThirdParty/doubango/tinyRTP -IFrameworks/ThirdParty/doubango/tinySAK -IFrameworks/ThirdParty/doubango/tinySDP -IFrameworks/ThirdParty/doubango/tinySIGCOMP -IFrameworks/ThirdParty/doubango/tinySIP -IFrameworks/ThirdParty/doubango/tinySMS -IFrameworks/ThirdParty/doubango/tinyXCAP -IFrameworks/ThirdParty/doubango/website -IFrameworks/ThirdParty/doubango/win32 -IFrameworks/MRVideoCall/Assets/Artwork/MRVideoCall.bundle -IFrameworks/MRVideoCall/Assets/Classes/SMTPLibrary -IFrameworks/MRVideoCall/Assets/Classes/UI -IFrameworks/ThirdParty/common-ngn-stack/services/impl -IFrameworks/ThirdParty/doubango/android-utils/java -IFrameworks/ThirdParty/doubango/bindings/_common -IFrameworks/ThirdParty/doubango/bindings/csharp -IFrameworks/ThirdParty/doubango/bindings/java -IFrameworks/ThirdParty/doubango/bindings/objc -IFrameworks/ThirdParty/doubango/bindings/perl -IFrameworks/ThirdParty/doubango/bindings/python -IFrameworks/ThirdParty/doubango/bindings/ruby -IFrameworks/ThirdParty/doubango/bindings/vs_2005 -IFrameworks/ThirdParty/doubango/bindings/winrt -IFrameworks/ThirdParty/doubango/images/OSes -IFrameworks/ThirdParty/doubango/images/sms -IFrameworks/ThirdParty/doubango/images/STUN -IFrameworks/ThirdParty/doubango/plugins/audio_opensles -IFrameworks/ThirdParty/doubango/plugins/audio_webrtc -IFrameworks/ThirdParty/doubango/plugins/pluginCUDA -IFrameworks/ThirdParty/doubango/plugins/pluginDirectShow -IFrameworks/ThirdParty/doubango/plugins/pluginWASAPI -IFrameworks/ThirdParty/doubango/plugins/pluginWinAudioDSP -IFrameworks/ThirdParty/doubango/plugins/pluginWinDD -IFrameworks/ThirdParty/doubango/plugins/pluginWinIPSecVista -IFrameworks/ThirdParty/doubango/plugins/pluginWinMF -IFrameworks/ThirdParty/doubango/Samples/C# -IFrameworks/ThirdParty/doubango/Samples/C++ -IFrameworks/ThirdParty/doubango/schemas/IANA\ \ XML\ Registry_fichiers -IFrameworks/ThirdParty/doubango/schemas/OMNA\ Schema-based\ Namespace\ Registry_fichiers -IFrameworks/ThirdParty/doubango/thirdparties/common -IFrameworks/ThirdParty/doubango/thirdparties/iphone -IFrameworks/ThirdParty/doubango/thirdparties/patches -IFrameworks/ThirdParty/doubango/thirdparties/s60 -IFrameworks/ThirdParty/doubango/thirdparties/scripts -IFrameworks/ThirdParty/doubango/tinyBFCP/include -IFrameworks/ThirdParty/doubango/tinyBFCP/src -IFrameworks/ThirdParty/doubango/tinyBFCP/test -IFrameworks/ThirdParty/doubango/tinyDAV/include -IFrameworks/ThirdParty/doubango/tinyDAV/src -IFrameworks/ThirdParty/doubango/tinyDAV/test -IFrameworks/ThirdParty/doubango/tinyDAV/winrt -IFrameworks/ThirdParty/doubango/tinyHTTP/abnf -IFrameworks/ThirdParty/doubango/tinyHTTP/include -IFrameworks/ThirdParty/doubango/tinyHTTP/ragel -IFrameworks/ThirdParty/doubango/tinyHTTP/src -IFrameworks/ThirdParty/doubango/tinyHTTP/test -IFrameworks/ThirdParty/doubango/tinyHTTP/winrt -IFrameworks/ThirdParty/doubango/tinyIPSec/src -IFrameworks/ThirdParty/doubango/tinyIPSec/test -IFrameworks/ThirdParty/doubango/tinyIPSec/winrt -IFrameworks/ThirdParty/doubango/tinyMEDIA/include -IFrameworks/ThirdParty/doubango/tinyMEDIA/ragel -IFrameworks/ThirdParty/doubango/tinyMEDIA/src -IFrameworks/ThirdParty/doubango/tinyMEDIA/test -IFrameworks/ThirdParty/doubango/tinyMEDIA/winrt -IFrameworks/ThirdParty/doubango/tinyMSRP/include -IFrameworks/ThirdParty/doubango/tinyMSRP/ragel -IFrameworks/ThirdParty/doubango/tinyMSRP/src -IFrameworks/ThirdParty/doubango/tinyMSRP/test -IFrameworks/ThirdParty/doubango/tinyMSRP/winrt -IFrameworks/ThirdParty/doubango/tinyNET/ragel -IFrameworks/ThirdParty/doubango/tinyNET/src -IFrameworks/ThirdParty/doubango/tinyNET/test -IFrameworks/ThirdParty/doubango/tinyNET/winrt -IFrameworks/ThirdParty/doubango/tinyROHC/include -IFrameworks/ThirdParty/doubango/tinyROHC/src -IFrameworks/ThirdParty/doubango/tinyRTP/include -IFrameworks/ThirdParty/doubango/tinyRTP/src -IFrameworks/ThirdParty/doubango/tinyRTP/test -IFrameworks/ThirdParty/doubango/tinySAK/src -IFrameworks/ThirdParty/doubango/tinySAK/test -IFrameworks/ThirdParty/doubango/tinySAK/winrt -IFrameworks/ThirdParty/doubango/tinySDP/abnf -IFrameworks/ThirdParty/doubango/tinySDP/docs_soa -IFrameworks/ThirdParty/doubango/tinySDP/include -IFrameworks/ThirdParty/doubango/tinySDP/ragel -IFrameworks/ThirdParty/doubango/tinySDP/src -IFrameworks/ThirdParty/doubango/tinySDP/test -IFrameworks/ThirdParty/doubango/tinySDP/winrt -IFrameworks/ThirdParty/doubango/tinySIGCOMP/asm -IFrameworks/ThirdParty/doubango/tinySIGCOMP/images -IFrameworks/ThirdParty/doubango/tinySIGCOMP/src -IFrameworks/ThirdParty/doubango/tinySIGCOMP/test -IFrameworks/ThirdParty/doubango/tinySIGCOMP/winrt -IFrameworks/ThirdParty/doubango/tinySIP/abnf -IFrameworks/ThirdParty/doubango/tinySIP/include -IFrameworks/ThirdParty/doubango/tinySIP/ragel -IFrameworks/ThirdParty/doubango/tinySIP/src -IFrameworks/ThirdParty/doubango/tinySIP/test -IFrameworks/ThirdParty/doubango/tinySIP/winrt -IFrameworks/ThirdParty/doubango/tinySMS/images -IFrameworks/ThirdParty/doubango/tinySMS/include -IFrameworks/ThirdParty/doubango/tinySMS/src -IFrameworks/ThirdParty/doubango/tinySMS/test -IFrameworks/ThirdParty/doubango/tinySMS/winrt -IFrameworks/ThirdParty/doubango/tinyXCAP/include -IFrameworks/ThirdParty/doubango/tinyXCAP/src -IFrameworks/ThirdParty/doubango/tinyXCAP/test -IFrameworks/ThirdParty/doubango/tinyXCAP/winrt -IFrameworks/ThirdParty/doubango/website/assets -IFrameworks/ThirdParty/doubango/win32/pthread -IFrameworks/MRVideoCall/Assets/Artwork/MRVideoCall.bundle/keypad_audio -IFrameworks/MRVideoCall/Assets/Artwork/MRVideoCall.bundle/sound -IFrameworks/MRVideoCall/Assets/Artwork/MRVideoCall.bundle/video_call -IFrameworks/ThirdParty/doubango/bindings/java/android -IFrameworks/ThirdParty/doubango/bindings/vs_2005/csharp -IFrameworks/ThirdParty/doubango/bindings/winrt/doubango_rt -IFrameworks/ThirdParty/doubango/plugins/pluginDirectShow/internals -IFrameworks/ThirdParty/doubango/plugins/pluginWinDD/internals -IFrameworks/ThirdParty/doubango/plugins/pluginWinMF/internals -IFrameworks/ThirdParty/doubango/Samples/C#/IPSec -IFrameworks/ThirdParty/doubango/Samples/C++/REGISTER -IFrameworks/ThirdParty/doubango/thirdparties/common/include -IFrameworks/ThirdParty/doubango/thirdparties/iphone/configure -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib -IFrameworks/ThirdParty/doubango/thirdparties/s60/configure -IFrameworks/ThirdParty/doubango/thirdparties/s60/include -IFrameworks/ThirdParty/doubango/thirdparties/scripts/ilbc -IFrameworks/ThirdParty/doubango/tinyBFCP/include/tinybfcp -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav -IFrameworks/ThirdParty/doubango/tinyDAV/src/audio -IFrameworks/ThirdParty/doubango/tinyDAV/src/bfcp -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs -IFrameworks/ThirdParty/doubango/tinyDAV/src/msrp -IFrameworks/ThirdParty/doubango/tinyDAV/src/t140 -IFrameworks/ThirdParty/doubango/tinyDAV/src/video -IFrameworks/ThirdParty/doubango/tinyHTTP/include/tinyhttp -IFrameworks/ThirdParty/doubango/tinyHTTP/src/auth -IFrameworks/ThirdParty/doubango/tinyHTTP/src/headers -IFrameworks/ThirdParty/doubango/tinyHTTP/src/parsers -IFrameworks/ThirdParty/doubango/tinyMEDIA/include/tinymedia -IFrameworks/ThirdParty/doubango/tinyMEDIA/src/content -IFrameworks/ThirdParty/doubango/tinyMSRP/include/tinymsrp -IFrameworks/ThirdParty/doubango/tinyMSRP/src/headers -IFrameworks/ThirdParty/doubango/tinyMSRP/src/parsers -IFrameworks/ThirdParty/doubango/tinyMSRP/src/session -IFrameworks/ThirdParty/doubango/tinyMSRP/test/test -IFrameworks/ThirdParty/doubango/tinyNET/src/dhcp -IFrameworks/ThirdParty/doubango/tinyNET/src/dhcp6 -IFrameworks/ThirdParty/doubango/tinyNET/src/dns -IFrameworks/ThirdParty/doubango/tinyNET/src/ice -IFrameworks/ThirdParty/doubango/tinyNET/src/stun -IFrameworks/ThirdParty/doubango/tinyNET/src/tls -IFrameworks/ThirdParty/doubango/tinyNET/src/turn -IFrameworks/ThirdParty/doubango/tinyRTP/include/tinyrtp -IFrameworks/ThirdParty/doubango/tinyRTP/src/rtcp -IFrameworks/ThirdParty/doubango/tinyRTP/src/rtp -IFrameworks/ThirdParty/doubango/tinySDP/include/tinysdp -IFrameworks/ThirdParty/doubango/tinySDP/src/headers -IFrameworks/ThirdParty/doubango/tinySDP/src/parsers -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip -IFrameworks/ThirdParty/doubango/tinySIP/src/api -IFrameworks/ThirdParty/doubango/tinySIP/src/authentication -IFrameworks/ThirdParty/doubango/tinySIP/src/dialogs -IFrameworks/ThirdParty/doubango/tinySIP/src/headers -IFrameworks/ThirdParty/doubango/tinySIP/src/parsers -IFrameworks/ThirdParty/doubango/tinySIP/src/sigcomp -IFrameworks/ThirdParty/doubango/tinySIP/src/transactions -IFrameworks/ThirdParty/doubango/tinySIP/src/transports -IFrameworks/ThirdParty/doubango/tinySMS/include/tinysms -IFrameworks/ThirdParty/doubango/tinySMS/src/rpdu -IFrameworks/ThirdParty/doubango/tinySMS/src/tpdu -IFrameworks/ThirdParty/doubango/tinyXCAP/include/tinyxcap -IFrameworks/ThirdParty/doubango/website/assets/css -IFrameworks/ThirdParty/doubango/website/assets/ico -IFrameworks/ThirdParty/doubango/website/assets/img -IFrameworks/ThirdParty/doubango/website/assets/js -IFrameworks/ThirdParty/doubango/bindings/vs_2005/csharp/test -IFrameworks/ThirdParty/doubango/bindings/winrt/doubango_rt/include -IFrameworks/ThirdParty/doubango/bindings/winrt/doubango_rt/src -IFrameworks/ThirdParty/doubango/plugins/pluginDirectShow/internals/wince -IFrameworks/ThirdParty/doubango/Samples/C#/IPSec/ipsec_app -IFrameworks/ThirdParty/doubango/Samples/C#/IPSec/ipsec_lib -IFrameworks/ThirdParty/doubango/Samples/C++/REGISTER/test -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libfreetype -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libxml2 -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libyuv -IFrameworks/ThirdParty/doubango/thirdparties/common/include/ogg -IFrameworks/ThirdParty/doubango/thirdparties/common/include/opus -IFrameworks/ThirdParty/doubango/thirdparties/common/include/speex -IFrameworks/ThirdParty/doubango/thirdparties/common/include/theora -IFrameworks/ThirdParty/doubango/thirdparties/common/include/vorbis -IFrameworks/ThirdParty/doubango/thirdparties/common/include/webrtc -IFrameworks/ThirdParty/doubango/thirdparties/common/include/wels -IFrameworks/ThirdParty/doubango/thirdparties/iphone/configure/openssl -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/g729b -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libavcodec -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libavdevice -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libavfilter -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libavformat -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libavutil -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libpostproc -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libswresample -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libswscale -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libyuv -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/net -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/opencore-amrnb -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/opencore-amrwb -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/openssl -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/speex -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/srtp -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/vpx -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/arm64 -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/armv6 -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/armv7 -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/armv7s -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/i386 -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/simulator -IFrameworks/ThirdParty/doubango/thirdparties/iphone/lib/x86_64 -IFrameworks/ThirdParty/doubango/thirdparties/s60/configure/libxml -IFrameworks/ThirdParty/doubango/thirdparties/s60/include/curl -IFrameworks/ThirdParty/doubango/thirdparties/s60/include/libxml -IFrameworks/ThirdParty/doubango/thirdparties/s60/include/smc -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/audio -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/bfcp -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/msrp -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/t140 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/video -IFrameworks/ThirdParty/doubango/tinyDAV/src/audio/alsa -IFrameworks/ThirdParty/doubango/tinyDAV/src/audio/coreaudio -IFrameworks/ThirdParty/doubango/tinyDAV/src/audio/directsound -IFrameworks/ThirdParty/doubango/tinyDAV/src/audio/oss -IFrameworks/ThirdParty/doubango/tinyDAV/src/audio/wasapi -IFrameworks/ThirdParty/doubango/tinyDAV/src/audio/waveapi -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/amr -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/bfcp -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/bv -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/dtmf -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/fec -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/g711 -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/g722 -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/g729 -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/gsm -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/h261 -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/h263 -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/h264 -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/ilbc -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/mp4ves -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/msrp -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/opus -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/speex -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/t140 -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/theora -IFrameworks/ThirdParty/doubango/tinyDAV/src/codecs/vpx -IFrameworks/ThirdParty/doubango/tinyDAV/src/video/gdi -IFrameworks/ThirdParty/doubango/tinyDAV/src/video/jb -IFrameworks/ThirdParty/doubango/tinyDAV/src/video/mf -IFrameworks/ThirdParty/doubango/tinyDAV/src/video/v4linux -IFrameworks/ThirdParty/doubango/tinyDAV/src/video/winm -IFrameworks/ThirdParty/doubango/tinyHTTP/include/tinyhttp/auth -IFrameworks/ThirdParty/doubango/tinyHTTP/include/tinyhttp/headers -IFrameworks/ThirdParty/doubango/tinyHTTP/include/tinyhttp/parsers -IFrameworks/ThirdParty/doubango/tinyMEDIA/include/tinymedia/content -IFrameworks/ThirdParty/doubango/tinyMSRP/include/tinymsrp/headers -IFrameworks/ThirdParty/doubango/tinyMSRP/include/tinymsrp/parsers -IFrameworks/ThirdParty/doubango/tinyMSRP/include/tinymsrp/session -IFrameworks/ThirdParty/doubango/tinyRTP/include/tinyrtp/rtcp -IFrameworks/ThirdParty/doubango/tinyRTP/include/tinyrtp/rtp -IFrameworks/ThirdParty/doubango/tinySDP/include/tinysdp/headers -IFrameworks/ThirdParty/doubango/tinySDP/include/tinysdp/parsers -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/api -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/authentication -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/dialogs -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/headers -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/parsers -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/sigcomp -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/transactions -IFrameworks/ThirdParty/doubango/tinySIP/include/tinysip/transports -IFrameworks/ThirdParty/doubango/tinySMS/include/tinysms/rpdu -IFrameworks/ThirdParty/doubango/tinySMS/include/tinysms/tpdu -IFrameworks/ThirdParty/doubango/website/assets/img/glyphicons -IFrameworks/ThirdParty/doubango/website/assets/js/google-code-prettify -IFrameworks/ThirdParty/doubango/bindings/vs_2005/csharp/test/Properties -IFrameworks/ThirdParty/doubango/Samples/C#/IPSec/ipsec_app/Properties -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libfreetype/freetype2 -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libxml2/libxml -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libyuv/libyuv -IFrameworks/ThirdParty/doubango/thirdparties/iphone/include/libyuv/libyuv -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/audio/alsa -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/audio/coreaudio -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/audio/directsound -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/audio/oss -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/audio/wasapi -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/audio/waveapi -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/amr -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/bfcp -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/bv -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/dtmf -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/fec -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/g711 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/g722 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/g729 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/gsm -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/h261 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/h263 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/h264 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/ilbc -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/mp4ves -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/msrp -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/opus -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/speex -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/t140 -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/theora -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/codecs/vpx -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/video/gdi -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/video/jb -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/video/mf -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/video/v4linux -IFrameworks/ThirdParty/doubango/tinyDAV/include/tinydav/video/winm -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libfreetype/freetype2/freetype -IFrameworks/ThirdParty/doubango/thirdparties/common/include/libfreetype/freetype2/freetype/config -I/Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/DerivedSources/x86_64 -I/Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/DerivedSources -F/Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Products/Debug-iphonesimulator -F/Users/james/Developer/dummyappios/iOSTest/Pods/Google-Mobile-Ads-SDK/GoogleMobileAdsSdkiOS-7.7.1 -F/Users/james/Developer/dummyappios/iOSTest/Setup/Model/FacebookSDK -F/Users/james/Developer/dummyappios/iOSTest/AdEngine/Tapjoy.embeddedframework -F/Users/james/Developer/dummyappios/iOSTest/AdEngine/MoPubSDK/AdNetworkSupport/Millennial/SDK -F/Users/james/Developer/dummyappios/iOSTest -isystem /Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public -isystem /Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/Google-Mobile-Ads-SDK -isystem /Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/RMUniversalAlert -isystem /Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/UIActionSheet+Blocks -isystem /Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/UIAlertController+Blocks -isystem /Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/UIAlertView+Blocks -isystem /Users/james/Developer/dummyappios/iOSTest/Pods/Headers/Public/mopub-ios-sdk -include /Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/PrecompiledHeaders/Dummyapp_Prefix-ctynolwwapskxefjizhtspapxrun/Dummyapp_Prefix.pch -MMD -MT dependencies -MF /Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/Objects-normal/x86_64/VoiceCallAction.d --serialize-diagnostics /Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/Objects-normal/x86_64/VoiceCallAction.dia -c /Users/james/Developer/dummyappios/iOSTest/Action/VoiceCallAction.m -o /Users/james/Library/Developer/Xcode/DerivedData/Dummyapp-faiocjbbymhdkyailfgkzrkpfiuc/Build/Intermediates/Dummyapp.build/Debug-iphonesimulator/Dummyapp.build/Objects-normal/x86_64/VoiceCallAction.o" "fzf"))

0.618137
(-2730 122 678 824)

Once I early exit like this, my history function becomes fairly fast again,

  (defun flx-all-completions (string table pred point)
    (let ((completion-ignore-case flx-completion-ignore-case))
      (pcase-let ((`(,all ,pattern ,prefix ,_suffix ,_carbounds)
                   (completion-substring--all-completions
                    string
                    table pred point
                    #'completion-flex--make-flex-pattern)))
        (when all
          (nconc
           (if (or (> (length string) flx--max-needle-len) (string= string ""))
               ;; Copy of `completion-flex-all-completions' when we don't do any
               ;; sorting.
               (completion-pcm--hilit-commonality pattern all)
             (mapcar
              (lambda (x)
                (setq x (copy-sequence x))
                (let* ((score
                        (cond
                         ((> (length x) 1000) ;; Exit, don't bother scoring.
                          '(0 0))
                         (:default
                          (if (fboundp 'flx-rs-score)
                              (flx-rs-score x string)
                            (flx-score x string flx-strings-cache))))))
                  (put-text-property 0 1 'completion-score
                                     (car score)
                                     x)
                  (setq x (flx-propertize x score)))
                x)
              all))
           (length prefix))))))
jojojames commented 2 years ago

@jcs090218 I wonder how much of a performance boost we'd get in practical scenarios with a cache. I'm thinking collections that start getting big will have a noticeable effect at some point.

(measure-time (dotimes (x 100000) x))
;; 0.025528

(measure-time
 (dotimes (x 100000)
   (flx-score "switch-to-buffer" "s-t-b" flx-strings-cache)))
;; 0.631230

(measure-time
 (dotimes (x 100000)
   (flx-rs-score "switch-to-buffer" "s-t-b")))
;; 1.130939

(measure-time
 (dotimes (x 100000)
   (flx-score "switch-to-buffer" "s-t-b")))
;; 2.837943

Of course, this is a flawed example, considering the cache will be hit every time in this case but does show that there might be possible performance improvements.

I'm guessing around 4000 candidates as it is right now will keep the same 'this is very fast' typing feeling (since completing-read is synchronous) and any more will slowly create a 'there's noticeable latency on every keystroke' feeling.

(measure-time
 (dotimes (x 4000)
   (flx-rs-score "switch-to-buffer" "s-t-b")))
;; 0.051238

This might be ignoring the fact that the initial abc* filtering on a collection that big may be more/same as the flx scoring itself.

jcs090218 commented 2 years ago

By seeing their document https://github.com/lewang/flx#memory-usage.

I don't think the cache is needed for flx-rs since it's a lot faster (16 times faster on my machine; I'm using Windows). Cache seems to be useless since your fuzzy matching will likely always be different. But as their document mentioned, it will still be faster than flx-rs since it will return an O(1) time after the first fuzzy search.

PR are welcome if you would like to give it a try. Some links might be helpful:

jcs090218 commented 2 years ago

I think I didn't really make a point in my previous post. In conclusion, I think with that much of speed up, without the cache is reasonable but nice to have.

jojojames commented 2 years ago

I think the cache will be super useful for repeated searches, e.g.

completing-read

a| [collection 1] ab| [collection 2] abc| [collection 3]

same completing-read session ab| (backspace) [cached collection 2]

or

completing read session 2

a| [cached collection 1] ab| [cached collection 2] abd| [collection 4]

and maybe an extension to the original flx with a file cache that can warm start the flx cache.

e.g.

Restart emacs: Populate flx cache with file cache

completing read session 3

a| [cached collection 1] ab| [cached collection 2] abd| [cached collection 4]

I may find the time to both learn rust & implement this though (was hoping our rust expert could do it ;)).

Do you remember quick locations where you changed the implementation (e.g. spots that were using cache that now aren't). Otherwise I may have to do an entire file diff to figure out where to implement this cache.

jcs090218 commented 2 years ago

Yeah, I think cache could be one of the missing feature from flx-rs. It's been a while I implement this rust module, and sorry I am not the Rust expert. 😓

But to answer your question, the entry point is at jcs090218/flx-rs/src/search.rs#L328. Once you are done with the cache implementation, you can change function:

https://github.com/jcs-elpa/flx-rs/blob/9af1aeec7722ee3e8506c86333a4c336fceed948/flx-rs.el#L55

with the cache parameter at the end.

The documentation from emacs-module-rs here.

Speeding up Emacs is one of the goals of dynamic modules. Too many back-and-forth conversions between Rust's data structures and Lisp's can defeat the purpose.

This is one of the main reason why I haven't start working on cache. I reckon the job isn't easy, and the result can be testable.

Another issue if the HashMap/hash-table. emacs-module-rs doesn't support hash-table conversion by default.

jojojames commented 2 years ago

This is one of the main reason why I haven't start working on cache. I reckon the job isn't easy, and the result can be testable.

Another issue if the HashMap/hash-table. emacs-module-rs doesn't support hash-table conversion by default.

I was thinking, at first, we don't expose the cache to the elisp machinery and use an internal cache instead.

I cooked a little up from digging through the flx code but my rust skills aren't up to par I think. The clone/copy/borrow semantics are tripping me up and I'm not sure how to easily declare a static variable to use in these functions.

pub static STRING_CACHE: HashMap<&str, FlxStrInfo> = HashMap::new();

#[derive(Clone)]
pub struct FlxStrInfo {
    // Generated through get_hash_for_string
    hash_for_string: HashMap<Option<u32>, VecDeque<Option<u32>>>,

    // Something that get_heatmap_str would return.
    heatmap: Vec<i32>,
}

impl FlxStrInfo {
    fn new() -> FlxStrInfo {
        FlxStrInfo {
            hash_for_string: HashMap::new(),
            heatmap: Vec::new(),
        }
    }
}

fn get_hash_for_string_2(
    hash: &mut FlxStrInfo,
    str: &str,
) {
    let mut result: HashMap<Option<u32>, VecDeque<Option<u32>>> = HashMap::new();
    let str_len: i32 = str.len() as i32;
    let mut index: i32 = str_len - 1;
    let mut char: Option<u32>;
    let mut down_char: Option<u32>;

    while 0 <= index {
        char = Some(str.chars().nth(index as usize).unwrap() as u32);

        if capital(char) {
            result
                .entry(char)
                .or_insert_with(VecDeque::new)
                .push_front(Some(index as u32));
            let valid: Option<char> = char::from_u32(char.unwrap());
            down_char = Some(valid.unwrap().to_lowercase().next().unwrap() as u32);
        } else {
            down_char = char;
        }

        result
            .entry(down_char)
            .or_insert_with(VecDeque::new)
            .push_front(Some(index as u32));

        index -= 1;
    }

    let mut heatmap: Vec<i32> = Vec::new();
    get_heatmap_str(&mut heatmap, str, None);

    hash.hash_for_string = result;
    hash.heatmap = heatmap;
}

pub fn flx_make_string_cache<'a>() -> HashMap<&'a str, FlxStrInfo> {
    return HashMap::new();
}

pub fn flx_process_cache<'a>(
    str: &'a str,
    cache: Option<&'a mut HashMap<&'a str, FlxStrInfo>>,
) -> FlxStrInfo {
    match cache {
        Some(c) => {
            match c.get(str).cloned() {
                Some(v) => {
                    return v;
                }

                None => {
                    let mut str_info: FlxStrInfo = FlxStrInfo::new();
                    get_hash_for_string_2(&mut str_info, str);
                    // FIXME: These clones are probably not good...
                    c.insert(str, str_info.clone());
                    return str_info.clone();
                }
            }
        }

        None => {
            let mut str_info: FlxStrInfo = FlxStrInfo::new();
            get_hash_for_string_2(&mut str_info, str);
            return str_info;
        }
    }
}
jcs090218 commented 2 years ago

@jojojames Hi, Do you want to move this to another issue then maybe we can discuss over there? So I don't get confused with the title. :)

jcs090218 commented 2 years ago

Let's move the discussion to the rust implementation repo, see https://github.com/jcs090218/flx-rs/issues/4.

jojojames commented 2 years ago

Sounds good, done.