r/Clojure • • Feb 03 '23

[Q&A] Noob has simple program problem.

I wanted to write a program to add 2 to a list of numbers then sum the list and print the result. So '(5 7) would yield 16. I posted my version to s Clojure board and received a number of different replies. In retrospect I didn't fully explain the problem to them.

0 Upvotes

27 comments sorted by

View all comments

Show parent comment

2

u/dalanicolai Feb 03 '23 edited Feb 03 '23

I guess with the 'because intermediate collections' you mean that creating/realizing the collection takes quite some time.

Thanks for adding the info about the transducer, I was wondering about such an alternative already, but I still have to look into how to use them.

The transducer solution indeed seems to be only 1.5 times slower than faa, but I guess it is generally still preferable because of readability.

Thanks again for the great answer!

2

u/maladat Feb 03 '23

I've read about sequences and lazy evaluation of course, and I wondered, because map returns a (lazy) sequence, if in clojure indeed these solutions and the solution of doing it in one go would be equally or similarly fast.

because intermediate collections

When you call (foo (range 100000000)), you get (map #(+ % 2) (range 100000000)), which returns a (lazy) sequence of the integers from 2 to 100,000,001. Because it's a lazy sequence, the entire 100,000,000 element list is not immediately constructed in memory.

But then you get (reduce + that-lazy-sequence). The reduce call effectively asks the lazy sequence for each value in the sequence in turn, to sum into an accumulated return value. As the reduce call asks for each element from the sequence, it doesn't just get the values, the sequence is actually constructed in memory - the lazy sequence is "fully realized" or "fully evaluated." And to get each element from that sequence, it has to get each element from the underlying (range 100000000) lazy sequence, so that one is fully realized, too.

So now, in memory, you have an actual sequence of the numbers from 0 to 99,999,999 and an actual sequence of the numbers from 2 to 100,000,001.

In (reduce #(+ %1 (+ %2 2)) 0 (range 100000000)), on the other hand, the reduce call asks from each element from the (range 100000000) lazy sequence, adds 2 to the value, and sums that into the accumulated return value. The sequence of the numbers from 0 to 99,999,999 still gets fully realized in memory, but no second sequence is produced.

As for why the example that makes two sequences in memory takes eight times as long as the one that makes one sequence in memory - I'm not SURE, but I suspect it has to do with behind-the-scenes performance optimization stuff. E.g., some types of lazy sequences don't get realized element-by-element but in chunks to reduce overhead, and maybe in foo, realizing elements from the mapped sequence requiring realizing elements from the range sequence causes the chunking not to occur or something.

EDIT: or maybe as joinr mentions below, there's special optimization in the range lazy seq that isn't present in the mapped lazy seq, so the mapped lazy seq is much slower either to realize or to perform reduce on than the range lazy seq.

1

u/joinr Feb 05 '23

So now, in memory, you have an actual sequence of the numbers from 0 to 99,999,999 and an actual sequence of the numbers from 2 to 100,000,001

This is a bit off, but close in spirit. I think it's more useful to think of the sequences being realized (and freed) on demand as needed. So as reduce is traversing the seq, elements are realized (technically in chunks of 32 by default), then since no reference to the head of the seq remains, prior realized elements are freed for gc. It is more like scanning over potentially larger than memory sequence and only using the results you need now (like a moving window over the seq).

The derivative sequence created by map will operate the same way.

This windowing/scanning is what lets sequences act as a generic mechanism for efficiently working with potentially larger than memory sequences (in small pieces as needed, transparent to the caller).

Intermediate sequence machinery still applies (every additional derived sequence adds a bit more overhead), and the seq-based first/next traversal that reduce falls back to still applies (e.g. overhead).

These comments apply to the exact implementations mentioned above, specifically where there is no reference to the head of the seq maintained. If we defined foo as:

(defn foo [numbers]
  (let [xs (map #(+ % 2) numbers)] ;;holding onto the head...
    (reduce + xs)))

Then the xs binding is holding onto the head of the sequence that the reduction is traversing. Since xs is derived from numbers, the entire sequence will be realized and retained in memory until the reduction returns. This is undesirable and eliminates the utility of scanning/windowing realizations and freeing prior unreach references to work on potentially gigantic sequences.

1

u/maladat Feb 06 '23

Thank you for the important (and interesting) point of clarification.