From b33e6caba92f8d48aa9cb4a577df6395a30cecc4 Mon Sep 17 00:00:00 2001 From: Andrey Listopadov Date: Mon, 15 Feb 2021 19:21:45 +0000 Subject: improve set iteration performance --- LICENSE | 2 +- doc/cljlib.md | 4 ++-- doc/macros.md | 4 ++-- init.fnl | 64 ++++++++++++++++++++++++++++++---------------------------- macros.fnl | 7 ++++--- tests/core.fnl | 4 ++-- 6 files changed, 44 insertions(+), 41 deletions(-) diff --git a/LICENSE b/LICENSE index 787c9d2..5d98ab5 100644 --- a/LICENSE +++ b/LICENSE @@ -1,6 +1,6 @@ MIT License -Copyright (c) 2020 Andrey Orst +Copyright (c) 2020-2021 Andrey Listopadov Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal diff --git a/doc/cljlib.md b/doc/cljlib.md index f1e7f5f..a06fca5 100644 --- a/doc/cljlib.md +++ b/doc/cljlib.md @@ -1,4 +1,4 @@ -# Cljlib (0.4.0) +# Cljlib (0.5.0) Fennel-cljlib - functions from Clojure's core.clj implemented on top of Fennel. @@ -1162,7 +1162,7 @@ syntax. Use `hash-set` function instead. --- -Copyright (C) 2020 Andrey Orst +Copyright (C) 2020-2021 Andrey Listopadov License: [MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE) diff --git a/doc/macros.md b/doc/macros.md index 7fa717c..fdced4e 100644 --- a/doc/macros.md +++ b/doc/macros.md @@ -1,4 +1,4 @@ -# Macros.fnl (0.4.0) +# Macros.fnl (0.5.0) Macros for Cljlib that implement various facilities from Clojure. **Table of contents** @@ -589,7 +589,7 @@ If `test` sets `binding` to non-`nil`, evaluates `body` in implicit --- -Copyright (C) 2020 Andrey Orst +Copyright (C) 2020-2021 Andrey Listopadov License: [MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE) diff --git a/init.fnl b/init.fnl index 009c0e5..7d5a7f9 100644 --- a/init.fnl +++ b/init.fnl @@ -1,6 +1,6 @@ -(local core {:_VERSION "0.4.0" +(local core {:_VERSION "0.5.0" :_LICENSE "[MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE)" - :_COPYRIGHT "Copyright (C) 2020 Andrey Orst" + :_COPYRIGHT "Copyright (C) 2020-2021 Andrey Listopadov" :_MODULE_NAME "cljlib" :_DESCRIPTION "Fennel-cljlib - functions from Clojure's core.clj implemented on top of Fennel. @@ -1091,15 +1091,17 @@ default." "{") set-indent (length prefix) indent-str (string.rep " " set-indent) - lines (icollect [i v (pairs Set)] - (.. (if (= i 1) "" indent-str) + lines (icollect [v (pairs Set)] + (.. indent-str (view v inspector (+ indent set-indent) true)))] - (tset lines 1 (.. prefix (or (. lines 1) ""))) + (tset lines 1 (.. prefix (string.gsub (or (. lines 1) "") "^%s+" ""))) (tset lines (length lines) (.. (. lines (length lines)) "}")) lines))) (fn ordered-set-newindex [Set] - "`__newindex` metamethod for ordered-set." + "`__newindex` metamethod for ordered-set. + +Updates order of all items when some key removed from set." (fn [t k v] (if (= nil v) (let [k (. Set k)] @@ -1137,28 +1139,29 @@ default." (lua :break))) (and res (= size (length s2)))) -(fn ordered-set-ipairs [Set] +(fn set->iseq [Set] + (collect [v k (pairs Set)] + (values k v))) + +(fn ordered-set-pairs [Set] "Returns stateless `ipairs` iterator for ordered sets." (fn [] - (fn set-next [t i] - (fn loop [t k] - (local (k v) (next t k)) - (if v (if (= v (+ 1 i)) - (values v k) - (loop t k)))) - (loop t)) - (values set-next Set 0))) - -(fn hash-set-ipairs [Set] + (var i 0) + (var iseq nil) + (fn set-next [t _] + (when (not iseq) + (set iseq (set->iseq Set))) + (set i (+ i 1)) + (let [v (. iseq i)] + (values v v))) + (values set-next Set nil))) + +(fn hash-set-pairs [Set] "Returns stateful `ipairs` iterator for hashed sets." (fn [] - (var i 0) - (fn iter [t _] - (var (k v) (next t)) - (for [j 1 i] - (set (k v) (next t k))) - (if k (do (set i (+ i 1)) - (values i k)))) + (fn iter [t k] + (let [v (next t k)] + (values v v))) (values iter Set nil))) (fn into-set [Set tbl] @@ -1252,7 +1255,7 @@ same size: ```" [& xs] (let [Set (setmetatable {} {:__index deep-index}) - set-ipairs (ordered-set-ipairs Set)] + set-pairs (ordered-set-pairs Set)] (var i 1) (each [_ val (ipairs xs)] (when (not (. Set val)) @@ -1268,8 +1271,7 @@ same size: :__len (set-length Set) :__index #(if (. Set $2) $2 nil) :__newindex (ordered-set-newindex Set) - :__ipairs set-ipairs - :__pairs set-ipairs + :__pairs set-pairs :__name "ordered set" :__fennelview viewset}))) @@ -1290,7 +1292,7 @@ supported by the Fennel reader, so you can't create sets with this syntax. Use `hash-set` function instead." [& xs] (let [Set (setmetatable {} {:__index deep-index}) - set-ipairs (hash-set-ipairs Set)] + set-pairs (hash-set-pairs Set)] (each [_ val (ipairs xs)] (when (not (. Set val)) (tset Set val true))) @@ -1304,8 +1306,7 @@ syntax. Use `hash-set` function instead." :__len (set-length Set) :__index #(if (. Set $2) $2 nil) :__newindex (hash-set-newindex Set) - :__ipairs set-ipairs - :__pairs set-ipairs + :__pairs set-pairs :__name "hash set" :__fennelview viewset}))) @@ -1327,4 +1328,5 @@ syntax. Use `hash-set` function instead." ;; LocalWords: cljlib Clojure's clj lua PUC mapv concat Clojure fn zs ;; LocalWords: defmulti multi arity eq metadata prepending variadic ;; LocalWords: args tbl LocalWords memoized referentially Andrey -;; LocalWords: Orst codepoints +;; LocalWords: Orst codepoints Listopadov metamethods nums multifn +;; LocalWords: stateful LuaJIT diff --git a/macros.fnl b/macros.fnl index f0e9134..81845fe 100644 --- a/macros.fnl +++ b/macros.fnl @@ -55,7 +55,7 @@ (fennel.metadata:set value k v))) -;;;;;;;;;;;;;;;;;;;;;;;;;; Runtime function builers ;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;; Runtime function builders ;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; TODO: This code should be shared with `init.fnl` @@ -1205,9 +1205,9 @@ Always run some side effect action: : defmethod : def : defonce - :_VERSION #"0.4.0" + :_VERSION #"0.5.0" :_LICENSE #"[MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE)" - :_COPYRIGHT #"Copyright (C) 2020 Andrey Orst" + :_COPYRIGHT #"Copyright (C) 2020-2021 Andrey Listopadov" :_DOC_ORDER #[:fn* :try :def :defonce :defmulti :defmethod @@ -1221,3 +1221,4 @@ Always run some side effect action: ;; LocalWords: defonce metadata metatable fac defmulti Umm defmethod ;; LocalWords: multimethods multimethod multifn REPL fnl AST Lua's ;; LocalWords: lua tostring str concat namespace ns Cljlib Clojure +;; LocalWords: TODO init Andrey Listopadov diff --git a/tests/core.fnl b/tests/core.fnl index ab62a4b..0220c06 100644 --- a/tests/core.fnl +++ b/tests/core.fnl @@ -234,8 +234,8 @@ (assert-eq (core.kvseq {123 456}) [[123 456]]) (assert-eq (core.kvseq {:a 1}) [[:a 1]]) (assert-eq (core.kvseq [0 0 0 10]) [[1 0] [2 0] [3 0] [4 10]]) - (assert-eq (core.kvseq (core.ordered-set :a :b :c)) [[1 :a] [2 :b] [3 :c]]) - (assert-eq (core.kvseq (core.hash-set :a)) [[1 :a]]) + (assert-eq (core.kvseq (core.ordered-set :a :b :c)) [[:a :a] [:b :b] [:c :c]]) + (assert-eq (core.kvseq (core.hash-set :a)) [[:a :a]]) (assert-eq (core.kvseq "abc") [[1 "a"] [2 "b"] [3 "c"]])) (testing "mapv" -- cgit v1.2.3