io.github.frenchy64.fully-satisfies.head-releasing
Variants of clojure.core functions (and internal helpers) that release the head of seqs earlier, enabling lower peak memory usage in some cases.
For example, many higher-order functions in this namespace release strong references to arguments before calling their function arguments. Realizing the following example would be prone to failure with an OutOfMemoryError using clojure.core/map because map retains a strong reference to takes-75-percent-of-heap when calling its function argument, which prevents memory from being reclaimed to create another value of that size.
(map (fn [takes-75-percent-of-heap] (if (< (rand) 0.5) takes-75-percent-of-heap (generate-another-value-taking-75-percent-of-heap))) [takes-75-percent-of-heap])
In contrast, using head-releasing/map, the garbage collector can reclaim takes-75-percent-of-heap while calculating (generate-another-value-taking-75-percent-of-heap) because head-releasing/map does not strongly reference takes-75-percent-of-heap at that point.
The basic implementation trick to achieving this is to call (rest s) on the seq currently being processed before calling (f (first f)), so the strong reference to (first f) is transferred from the higher-order function to f during the call to f.
There are potential caveats to this approach: https://clojure.org/reference/lazy#_extension_iseqs If the underlying ISeq implementation defines rest in terms of next as in the article, then the functions in this namespace will force two seq elements into memory simultaneously. For example, the call below will throw an OutOfMemoryError before the fn is called because both elements of the seq will be realized.
(map (fn [takes-75-percent-of-heap] nil) (lazy-seq-where-rest-calls-next (cons (->takes-75-percent-of-heap) (lazy-seq [(->takes-75-percent-of-heap)]))))
Infinite lazy seqs such as cycle or repeat always hold strong references to all their elements, so the functions in this namespace will have no affect in the memory usage of processing these seqs.
Another caveat is that the functions here are perhaps more useful as validation of the leaky-seq-detection framework and for pedalogical purposes about sequences than as significant bump in real-world expressivity. See the tests for how these implementations were verified: io.github.frenchy64.fully-satisfies.leaky-seq-detection-test
The author of this namespace can only speculate why the original functions were written this way. Perhaps the idea of a fn releasing a strong reference to one of its arguments was too rare to risk the caveats in using the default implementation of ISeq. Chunked seqs are also so prevalent and have much higher memory requirements that the optimizations in this namespace might have been deemed insignificant. For example, map processing a chunk of 32 must have enough memory to hold both 32 elements of the input collection and 32 elements of the output collection simultaneously. Chunked seqs also make programs such as the above unidiomatic since they are so difficult to get right (see the hoops math.combinatorics jumps through to reduce the 32+32 elements of the previous example to 32+1).
At the very least, this work helps crystallize the differences between rest and next---or more precisely, their similarities: while rest does not realize the next element, nor tell us whether a seq has more elements, it is still an eager operation whose result, like next, releases a strong reference to the first element of the seq.
Variants of clojure.core functions (and internal helpers)
that release the head of seqs earlier, enabling lower peak memory
usage in some cases.
For example, many higher-order functions in this namespace release strong
references to arguments before calling their function arguments.
Realizing the following example would be prone to failure with an OutOfMemoryError using
clojure.core/map because map retains a strong reference to takes-75-percent-of-heap
when calling its function argument, which prevents memory from being reclaimed to create
another value of that size.
(map (fn [takes-75-percent-of-heap]
(if (< (rand) 0.5)
takes-75-percent-of-heap
(generate-another-value-taking-75-percent-of-heap)))
[takes-75-percent-of-heap])
In contrast, using head-releasing/map, the garbage collector can reclaim takes-75-percent-of-heap
while calculating (generate-another-value-taking-75-percent-of-heap) because
head-releasing/map does not strongly reference takes-75-percent-of-heap at that point.
The basic implementation trick to achieving this is to call (rest s) on the seq currently
being processed _before_ calling (f (first f)), so the strong reference to (first f)
is transferred from the higher-order function to f during the call to f.
There are potential caveats to this approach: https://clojure.org/reference/lazy#_extension_iseqs
If the underlying ISeq implementation defines rest in terms of next as in the article, then the
functions in this namespace will force two seq elements into memory simultaneously.
For example, the call below will throw an OutOfMemoryError before the fn is called because both
elements of the seq will be realized.
(map (fn [takes-75-percent-of-heap] nil)
(lazy-seq-where-rest-calls-next
(cons (->takes-75-percent-of-heap)
(lazy-seq [(->takes-75-percent-of-heap)]))))
Infinite lazy seqs such as cycle or repeat always hold strong references to all their elements, so
the functions in this namespace will have no affect in the memory usage of processing these seqs.
Another caveat is that the functions here are perhaps more useful as
validation of the leaky-seq-detection framework and for pedalogical purposes about sequences
than as significant bump in real-world expressivity.
See the tests for how these implementations were verified:
io.github.frenchy64.fully-satisfies.leaky-seq-detection-test
The author of this namespace can only speculate why the original functions were written this way.
Perhaps the idea of a fn releasing a strong reference to one of its arguments was too rare to risk
the caveats in using the default implementation of ISeq. Chunked seqs are also so prevalent
and have much higher memory requirements that the optimizations in this namespace might
have been deemed insignificant. For example, map processing a chunk of 32 must have enough memory
to hold both 32 elements of the input collection and 32 elements of the output collection simultaneously.
Chunked seqs also make programs such as the above unidiomatic since they are so difficult to get right
(see the hoops math.combinatorics jumps through to reduce the 32+32 elements of the previous example to
32+1).
At the very least, this work helps crystallize the differences between rest and next---or
more precisely, their similarities: while rest does not realize the next element, nor tell us whether
a seq has more elements, it is still an eager operation whose result, like next, releases a strong
reference to the first element of the seq.every?clj
(every? pred coll)Returns true if (pred x) is logical true for every x in coll, else false.
head-releasing/every? is additionally:
- thread-safe for mutable collections
- does not hold strong reference to argument of pred when it is called.
Returns true if (pred x) is logical true for every x in coll, else false. head-releasing/every? is additionally: - thread-safe for mutable collections - does not hold strong reference to argument of pred when it is called.
keepclj
(keep f)(keep f coll)Returns a lazy sequence of the non-nil results of (f item). Note, this means false return values will be included. f must be free of side-effects. Returns a transducer when no collection is provided.
Additionally, head-releasing/keep does not hold a strong reference to the argument of f when it is called (unless a single chunked seq coll is provided).
Returns a lazy sequence of the non-nil results of (f item). Note, this means false return values will be included. f must be free of side-effects. Returns a transducer when no collection is provided. Additionally, head-releasing/keep does not hold a strong reference to the argument of f when it is called (unless a single chunked seq coll is provided).
keep-indexedclj
(keep-indexed f)(keep-indexed f coll)Returns a lazy sequence of the non-nil results of (f index item). Note, this means false return values will be included. f must be free of side-effects. Returns a stateful transducer when no collection is provided.
Additionally, head-releasing/keep-indexed does not hold a strong reference to the argument of f when it is called (unless a single chunked seq coll is provided).
Returns a lazy sequence of the non-nil results of (f index item). Note, this means false return values will be included. f must be free of side-effects. Returns a stateful transducer when no collection is provided. Additionally, head-releasing/keep-indexed does not hold a strong reference to the argument of f when it is called (unless a single chunked seq coll is provided).
mapclj
(map f)(map f coll)(map f c1 c2)(map f c1 c2 c3)(map f c1 c2 c3 & colls)Returns a lazy sequence consisting of the result of applying f to the set of first items of each coll, followed by applying f to the set of second items in each coll, until any one of the colls is exhausted. Any remaining items in other colls are ignored. Function f should accept number-of-colls arguments. Returns a transducer when no collection is provided.
Additionally, head-releasing/map does not hold a strong reference to the arguments of f when it is called (unless a single chunked seq coll is provided).
Returns a lazy sequence consisting of the result of applying f to the set of first items of each coll, followed by applying f to the set of second items in each coll, until any one of the colls is exhausted. Any remaining items in other colls are ignored. Function f should accept number-of-colls arguments. Returns a transducer when no collection is provided. Additionally, head-releasing/map does not hold a strong reference to the arguments of f when it is called (unless a single chunked seq coll is provided).
map-indexedclj
(map-indexed f)(map-indexed f coll)Returns a lazy sequence consisting of the result of applying f to 0 and the first item of coll, followed by applying f to 1 and the second item in coll, etc, until coll is exhausted. Thus function f should accept 2 arguments, index and item. Returns a stateful transducer when no collection is provided.
Additionally, head-releasing/map-indexed does not hold a strong reference to the argument of f when it is called (unless a single chunked seq coll is provided).
Returns a lazy sequence consisting of the result of applying f to 0 and the first item of coll, followed by applying f to 1 and the second item in coll, etc, until coll is exhausted. Thus function f should accept 2 arguments, index and item. Returns a stateful transducer when no collection is provided. Additionally, head-releasing/map-indexed does not hold a strong reference to the argument of f when it is called (unless a single chunked seq coll is provided).
mapcatclj
(mapcat f)(mapcat f & colls)Returns the result of applying concat to the result of applying map to f and colls. Thus function f should return a collection. Returns a transducer when no collections are provided.
Additionally, head-releasing/mapcat does not hold strong references to the arguments of f when it is called (unless a single chunked seq coll is provided).
Returns the result of applying concat to the result of applying map to f and colls. Thus function f should return a collection. Returns a transducer when no collections are provided. Additionally, head-releasing/mapcat does not hold strong references to the arguments of f when it is called (unless a single chunked seq coll is provided).
naive-seq-reduceclj
(naive-seq-reduce s f val)Reduces a seq, ignoring any opportunities to switch to a more specialized implementation.
Additionally, head-releasing/naive-seq-reduce does not retain a strong reference to the arguments of f when it is called.
Reduces a seq, ignoring any opportunities to switch to a more specialized implementation. Additionally, head-releasing/naive-seq-reduce does not retain a strong reference to the arguments of f when it is called.
not-any?clj
(not-any? pred coll)Returns false if (pred x) is logical true for any x in coll, else true.
Additionally, head-releasing/not-any? does not hold a strong reference to the argument of pred when it is called.
Returns false if (pred x) is logical true for any x in coll,
else true.
Additionally, head-releasing/not-any? does not hold a strong reference
to the argument of pred when it is called.not-every?clj
(not-every? pred coll)Returns false if (pred x) is logical true for every x in coll, else true.
Additionally, head-releasing/not-every? does not hold a strong reference to the argument of pred when it is called.
Returns false if (pred x) is logical true for every x in coll, else true. Additionally, head-releasing/not-every? does not hold a strong reference to the argument of pred when it is called.
someclj
(some pred coll)Returns the first logical true value of (pred x) for any x in coll, else nil. One common idiom is to use a set as pred, for example this will return :fred if :fred is in the sequence, otherwise nil: (some #{:fred} coll)
Additionally, head-releasing/some does not hold a strong reference to the argument of pred when it is called.
Returns the first logical true value of (pred x) for any x in coll,
else nil. One common idiom is to use a set as pred, for example
this will return :fred if :fred is in the sequence, otherwise nil:
(some #{:fred} coll)
Additionally, head-releasing/some does not hold a strong reference
to the argument of pred when it is called.cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close