Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.lisp > #60742 > unrolled thread

Resources to learn common lisp?

Back to article view | Back to comp.lang.lisp

Contents

  Resources to learn common lisp? Mario Rosell <mario@mariorosell.es> - 2026-02-20 22:53 +0100
    Re: Resources to learn common lisp? Ben Bacarisse <ben@bsb.me.uk> - 2026-02-20 22:00 +0000
      Re: Resources to learn common lisp? Mario Rosell <mario@mariorosell.es> - 2026-02-21 12:25 +0100
        Re: Resources to learn common lisp? Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-21 10:24 -0500
        Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-02-21 21:30 +0000
          Re: Resources to learn common lisp? Mario Rosell <mario@mariorosell.es> - 2026-02-22 01:08 +0100
            Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-02-22 04:59 +0000
              Re: Resources to learn common lisp? Madhu <enometh@meer.net> - 2026-02-22 10:59 +0530
                Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-02-22 21:48 +0000
                  Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-08 12:43 -0400
          Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-08 12:41 -0400
            Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-08 20:02 +0000
              Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-09 00:23 -0400
                Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-09 06:28 +0000
                  Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-09 06:32 +0000
                    Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-10 12:27 -0400
                      Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-11 17:33 +0000
                  Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-10 12:16 -0400
              Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-09 06:53 +0000
                Re: Resources to learn common lisp? Axel Reichert <mail@axel-reichert.de> - 2026-06-09 12:07 +0200
                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-10 00:14 +0000
                Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-11 17:22 +0000
                Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-13 13:59 -0700
                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 00:55 +0000
                    Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-14 01:43 -0700
                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 05:45 +0000
            Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-09 00:35 +0000
        Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-08 12:37 -0400
          Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-09 00:33 +0000
            Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-09 00:22 -0400
            Re: Resources to learn common lisp? Alan Bawden <alan@csail.mit.edu> - 2026-06-09 01:22 -0400
              Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-09 06:17 +0000
              Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-09 06:50 +0000
                Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-10 12:40 -0400
                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-11 00:26 +0000
                  Re: Resources to learn common lisp? George Neuner <gneuner2@comcast.net> - 2026-06-11 05:27 -0400
              Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-10 12:24 -0400
                Re: Resources to learn common lisp? George Neuner <gneuner2@comcast.net> - 2026-06-11 05:57 -0400
                Re: Resources to learn common lisp? Alan Bawden <alan@csail.mit.edu> - 2026-06-11 21:07 -0400
                  Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-12 13:06 +0000
                    Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-13 00:13 +0000
                      Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-13 07:25 +0000
                        Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-13 08:25 +0000
                          Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-13 08:46 +0000
                            Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-13 08:52 +0000
                              Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 05:57 +0000
                                Re: Resources to learn common lisp? Nuno Silva <nunojsilva@invalid.invalid> - 2026-06-15 10:10 +0100
                            Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 05:56 +0000
                              Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-16 11:46 +0000
                    Re: Resources to learn common lisp? Alan Bawden <alan@csail.mit.edu> - 2026-06-13 00:55 -0400
                      Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-13 07:43 +0000
                  Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-13 13:09 -0700
                    Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 01:02 +0000
                    Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-16 10:12 +0000
                Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-12 12:42 +0000
            Re: Resources to learn common lisp? Stefan Monnier <monnier@iro.umontreal.ca> - 2026-06-09 09:36 -0400
              Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-10 00:06 +0000
                Re: Resources to learn common lisp? Stefan Monnier <monnier@iro.umontreal.ca> - 2026-06-10 08:43 -0400
                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-11 00:22 +0000
                    Re: Resources to learn common lisp? Stefan Monnier <monnier@iro.umontreal.ca> - 2026-06-11 08:57 -0400
                      Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-12 00:16 +0000
                    Re: Resources to learn common lisp? antispam@fricas.org (Waldek Hebisch) - 2026-06-15 01:15 +0000
                      Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-15 05:42 +0000
                        Re: Resources to learn common lisp? antispam@fricas.org (Waldek Hebisch) - 2026-06-15 11:19 +0000
                          Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-16 00:18 +0000
                            Re: Resources to learn common lisp? antispam@fricas.org (Waldek Hebisch) - 2026-06-16 03:27 +0000
                              Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-16 01:25 -0700
                Re: Resources to learn common lisp? George Neuner <gneuner2@comcast.net> - 2026-06-11 06:37 -0400
                  Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-13 13:30 -0700
                    Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 00:58 +0000
                      Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-14 01:46 -0700
                        Re: Resources to learn common lisp? George Neuner <gneuner2@comcast.net> - 2026-06-15 06:59 -0400
                          Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-15 12:25 -0700
                Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-11 17:42 +0000
                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-12 00:16 +0000
                    Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-12 12:34 +0000
                      Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-13 00:11 +0000
                        Re: Resources to learn common lisp? George Neuner <gneuner2@comcast.net> - 2026-06-13 04:06 -0400
                          Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-13 13:37 -0700
                            Re: Resources to learn common lisp? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-06-13 21:25 +0000
                              Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-13 15:26 -0700
                                Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 05:37 +0000
                                  Re: Resources to learn common lisp? antispam@fricas.org (Waldek Hebisch) - 2026-06-15 01:34 +0000
                                    Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-15 05:43 +0000
                                      Re: Resources to learn common lisp? antispam@fricas.org (Waldek Hebisch) - 2026-06-15 11:23 +0000
                                        Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-16 00:23 +0000
                                          Re: Resources to learn common lisp? antispam@fricas.org (Waldek Hebisch) - 2026-06-16 03:29 +0000
                                            Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-16 04:59 +0000
                                    Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-16 13:34 +0000
                        Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-13 08:36 +0000
                          Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 01:43 +0000
                            Re: Resources to learn common lisp? Stefan Monnier <monnier@iro.umontreal.ca> - 2026-06-14 10:36 -0400
                              Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 23:55 +0000
                                Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-14 18:04 -0700
                                  Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-16 12:33 +0000
                                Re: Resources to learn common lisp? Stefan Monnier <monnier@iro.umontreal.ca> - 2026-06-15 09:51 -0400
                                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-16 00:23 +0000
                                    Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-16 03:14 -0700
                            Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-14 13:14 -0700
                            Re: Resources to learn common lisp? tfb <no_email@invalid.invalid> - 2026-06-16 11:46 +0000
                Re: Resources to learn common lisp? Paul Rubin <no.email@nospam.invalid> - 2026-06-13 13:22 -0700
                  Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-14 01:55 +0000
    Re: Resources to learn common lisp? tpeplt <tpeplt@gmail.com> - 2026-02-20 17:44 -0500
      Re: Resources to learn common lisp? Mario Rosell <mario@mariorosell.es> - 2026-02-21 12:30 +0100
    Re: Resources to learn common lisp? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-02-20 23:50 +0000
      Re: Resources to learn common lisp? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-02-21 00:24 +0000
        Re: Resources to learn common lisp? Andreas Eder <a_eder_muc@web.de> - 2026-02-21 11:36 +0100
        Re: Resources to learn common lisp? Mario Rosell <mario@mariorosell.es> - 2026-02-21 12:44 +0100
    Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-03-31 17:47 -0400
      Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-03-31 23:41 +0000
      Re: Resources to learn common lisp? tpeplt <tpeplt@gmail.com> - 2026-04-01 13:23 -0400
    Re: Resources to learn common lisp? Peri Didaskalou <pfd@torfree.net> - 2026-05-01 10:52 -0400
    Re: Resources to learn common lisp? Peri Didaskalou <pfd@torfree.net> - 2026-05-01 10:57 -0400
    Re: Resources to learn common lisp? Peri Didaskalou <pfd@torfree.net> - 2026-05-01 11:06 -0400
    Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-01 14:56 -0400
      Re: Resources to learn common lisp? "Robert B. Carleton" <rbc@rbcarleton.net> - 2026-06-01 23:02 +0000
        Re: Resources to learn common lisp? steve g <sgonedes1977@gmail.com> - 2026-06-02 21:32 -0400
          Re: Resources to learn common lisp? Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-06-03 03:16 +0000

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6  Next page →

#60856

On Thu, 11 Jun 2026 08:57:35 -0400, Stefan Monnier wrote:

> Lawrence D’Oliveiro [2026-06-11 00:22:36] wrote:
>>
>> Feel free to show any performance measures that back up your claim
>> -- particularly memory usage.
>
> How could memory usage measures back up my claim, which is about
> speed?

Yeah, too bad.

[toc] | [prev] | [next] | [standalone]

#60899

Lawrence D’Oliveiro <ldo@nz.invalid> wrote:
> On Tue, 09 Jun 2026 09:36:50 -0400, Stefan Monnier wrote:
> 
>> On Wed, 10 Jun 2026 00:06:17 -0000 (UTC), Lawrence D’Oliveiro wrote:
>>>
>>> On Tue, 09 Jun 2026 09:36:50 -0400, Stefan Monnier wrote:
>>>
>>>> Probably not "for speed": it takes a significant amount of work to
>>>> make a reference-counting system that's competitive (speedwise)
>>>> with a tracing GC, because there tend to be *many* refcount
>>>> updates (and it gets worse if you support concurrency, where most
>>>> of those updates need to be made atomic).
>>>
>>> But those refcount updates are on live objects, which means they
>>> are more likely to reside in some level of CPU cache.
>>>
>>> Whereas a garbage collector, by design, is spending much of its
>>> time hitting long-dead objects, which would likely have long since
>>> disappeared from the cache. That’s going to add an order of
>>> magnitude or two to your execution time -- which is why we have
>>> caches in the first place.
>>
>> AFAIK, real-life usually disagrees with your analysis, which is why
>> refcount is rarely used in practice for implementations of languages
>> with automatic memory management.
> 
> Feel free to show any performance measures that back up your claim --
> particularly memory usage. I would say the only reason the Python
> approach hasn’t been done before now is because it’s hard to do --
> pure brute-force GC has always simply been the path of least
> resistance.

On equvalent programs built from low-level operations 'sbcl'
routinely gets _much_ better performance than Python.  'sbcl'
has nice profiler which (among other) indicates how much time
is spent in garbage collector.  Usually garbage collection
has modest impact on execution speed (say about 10-30%).
Of course, if program is consing like crazy, then cost of
garbage collection will grow.  But if you try reference counting
you will spent even more time.

For Python cost of reference counting does not matter too much
simply because cost of interpretation is too big.  To get good
speed in Python you want to pass work to C/C++ code which is
is not going to do either GC or reference counting.

Concerning least resistance: in languages like Perl or Python
vast majority of data structures is (or was) noncyclic.  In
such case reference counting is easy to implement.

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#60901

On Mon, 15 Jun 2026 01:15:12 -0000 (UTC), Waldek Hebisch wrote:

> On equvalent programs built from low-level operations 'sbcl'
> routinely gets _much_ better performance than Python.

Is this with similar memory consumption?

[toc] | [prev] | [next] | [standalone]

#60907

Lawrence D’Oliveiro <ldo@nz.invalid> wrote:
> On Mon, 15 Jun 2026 01:15:12 -0000 (UTC), Waldek Hebisch wrote:
> 
>> On equvalent programs built from low-level operations 'sbcl'
>> routinely gets _much_ better performance than Python.
> 
> Is this with similar memory consumption?

It is hard to compare and too many things differ.  All other
things being equal I would expect reference counting to have
lower memory use.  GC similar to used in sbcl at peak needs
about 3-4 times more memory than amount of live data.
Reference counting needs space for counts (50% increase of
size for typical cons cell) and in non-moving variant looses
some space do to fragmentation.  Fragmentation in worst case
may be quite significant, but usually is moderarte.

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#60912

On Mon, 15 Jun 2026 11:19:10 -0000 (UTC), Waldek Hebisch wrote:

> Lawrence D’Oliveiro <ldo@nz.invalid> wrote:
>>
>> On Mon, 15 Jun 2026 01:15:12 -0000 (UTC), Waldek Hebisch wrote:
>>
>>> On equvalent programs built from low-level operations 'sbcl'
>>> routinely gets _much_ better performance than Python.
>>
>> Is this with similar memory consumption?
>
> It is hard to compare and too many things differ.

But you were not so reticent above about claiming “routinely gets
_much_ better performance”, were you?

> All other things being equal I would expect reference counting to
> have lower memory use. GC similar to used in sbcl at peak needs
> about 3-4 times more memory than amount of live data. Reference
> counting needs space for counts (50% increase of size for typical
> cons cell) and in non-moving variant looses some space do to
> fragmentation. Fragmentation in worst case may be quite significant,
> but usually is moderarte.

Given that languages like Python have much higher-level data
structures than simple cons cells, and also encourage you to use them,
the extra space overhead in practice is minimal. Also don’t forget the
gain from not having all those “CDR” fields that make you do
pointer-chasing all the time.

[toc] | [prev] | [next] | [standalone]

#60915

Lawrence D’Oliveiro <ldo@nz.invalid> wrote:
> On Mon, 15 Jun 2026 11:19:10 -0000 (UTC), Waldek Hebisch wrote:
> 
>> Lawrence D’Oliveiro <ldo@nz.invalid> wrote:
>>>
>>> On Mon, 15 Jun 2026 01:15:12 -0000 (UTC), Waldek Hebisch wrote:
>>>
>>>> On equvalent programs built from low-level operations 'sbcl'
>>>> routinely gets _much_ better performance than Python.
>>>
>>> Is this with similar memory consumption?
>>
>> It is hard to compare and too many things differ.
> 
> But you were not so reticent above about claiming “routinely gets
> _much_ better performance”, were you?

I have a lot of data about runtime and by "preformance" I mean
runtime.  I have rather sparse data about memory use (especially
about Python memory use).

And in case you missed it: limited percentage of time spent in
sbcl GC is not due to slowness of other code.  In fact the
opposite is true: since other code is fast pressure on garbage
collector is bigger.

>> All other things being equal I would expect reference counting to
>> have lower memory use. GC similar to used in sbcl at peak needs
>> about 3-4 times more memory than amount of live data. Reference
>> counting needs space for counts (50% increase of size for typical
>> cons cell) and in non-moving variant looses some space do to
>> fragmentation. Fragmentation in worst case may be quite significant,
>> but usually is moderarte.
> 
> Given that languages like Python have much higher-level data
> structures than simple cons cells, and also encourage you to use them,
> the extra space overhead in practice is minimal. Also don’t forget the
> gain from not having all those “CDR” fields that make you do
> pointer-chasing all the time.

That "higher-level data structures" is part of complication.
I did not look at Python internal data structures, but
I looked at Perl data structures, and when I looked at them
they were extremaly wasteful.  'sbcl' data structures are
not super-efficient, but not bad.

Have you looked at space needed by say binary tree in Python
(I did not)?  Node can be represented as a struct which
AFAICS in sbcl need 3 machine words.  Alternatively one
can use a vector (also 3 machine words) or two cons cells
(4 machine words).

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#60918

antispam@fricas.org (Waldek Hebisch) writes:
> Have you looked at space needed by say binary tree in Python

Python likes to use arrays and dictionaries for almost everything.
Those are implemented in C and optimized pretty well, though mostly for
speed.  Integers are boxed and while (iirc) -1 through 100 are
preallocated, the rest get consed as needed and reclaimed later.

Of course in the olden days there were very compact Lisp representations
like BIBOP (Big Bag of Pages) for memory-starved machines.  So you'd
have a page full of cons cells, a page full of symbols, etc.  That way
you didn't need type tags: the address would tell you what the type was.

These days the heap size of a running program usually isn't that
important, for reasons I described earlier.  The computer's memory is
full of stuff like video frames and the program heap coexists with that.

[toc] | [prev] | [next] | [standalone]

#60850

On Wed, 10 Jun 2026 00:06:17 -0000 (UTC), Lawrence D´Oliveiro
<ldo@nz.invalid> wrote:

>On Tue, 09 Jun 2026 09:36:50 -0400, Stefan Monnier wrote:
>
>> On Tue, 9 Jun 2026 00:33:44 -0000 (UTC), Lawrence D’Oliveiro wrote:
>>>
>>> Languages like Perl and Python try for a hybrid
>>> reference-counted/garbage-collected approach, for speed and also
>>> more deterministic memory usage in many common scenarios.
>>
>> Probably not "for speed": it takes a significant amount of work to
>> make a reference-counting system that's competitive (speedwise) with
>> a tracing GC, because there tend to be *many* refcount updates (and
>> it gets worse if you support concurrency, where most of those
>> updates need to be made atomic).
>
>But those refcount updates are on live objects, which means they are
>more likely to reside in some level of CPU cache.

Depends. Often with reference counting systems linked structures -
lists and trees - are just stuck on the relevant[*] free list and are
not deconstructed until/unless the nodes are needed for new
allocations.  By that time they are no longer in cache.

[*] many systems use list based allocators that are designed to
provide fixed sized blocks for some number of commonly used sizes,
backed by a general best fit allocator if nothing else fits. E.g., if
you ask for 96 bytes, you may get a 128 byte block.


>Whereas a garbage collector, by design, is spending much of its time
>hitting long-dead objects, which would likely have long since
>disappeared from the cache.

That depends on the type of GC. 

Mark-sweep collectors must make (at least) one pass over the entire
heap to locate and recycle dead objects. They touch every heap object
once and live objects twice.

However mark-compact and semispace copying collectors touch only live
objects (and touch them only once).  In these systems dead objects are
simply abandoned and their memory is reclaimed by being overwritten in
subsequent allocations.


>That’s going to add an order of magnitude or two to your execution
>time -- which is why we have caches in the first place.

Sweeping is a sequential walk through the heap - the access pattern is
highly predictable (to the CPU) and quite fast ... which is why
mark-sweep systems still are used.  Marking live data often takes much
longer because it jumps around.  

Copying is similar to marking in that it jumps around, but copying
eliminates the need to sweep afterward.

[toc] | [prev] | [next] | [standalone]

#60875

George Neuner <gneuner2@comcast.net> writes:
> Copying is similar to marking in that it jumps around, but copying
> eliminates the need to sweep afterward.

I remember that GHC's generational GC is tuned so that the most frequent
copy operations are in blocks small enough to fit in the CPU L2 cache,
256K or whatever.  I expect that's typical of modern GC's but I haven't
been on top of things.

Fwiw SPITBOL has something like a generational mark-sweep GC that it
says it got from Lisp 2.0.  Lisp 2.0 is now otherwise completely obscure
from what I can tell.  Old objects get compacted down to a region called
the "sediment" which is not scanned in most later GC operations, if I
remember it right.  There are occasional bigger GC's where the sediment
also gets scanned.  It seems like a cool idea but I haven't investigated
it that much.

[toc] | [prev] | [next] | [standalone]

#60881

On Sat, 13 Jun 2026 13:30:31 -0700, Paul Rubin wrote:

> I remember that GHC's generational GC is tuned so that the most
> frequent copy operations are in blocks small enough to fit in the
> CPU L2 cache, 256K or whatever.

That “or whatever” is a bit of a problem though, isn’t it?

Also, it’s pointless to break up sequential data access into blocks
small enough to fit into the cache, if they’re only going to be read
once in the cache before being replaced by the next block. Caches are
all about speeding up repeated accesses to the same data.

[toc] | [prev] | [next] | [standalone]

#60891

Lawrence D’Oliveiro <ldo@nz.invalid> writes:
>> CPU L2 cache, 256K or whatever.
> That “or whatever” is a bit of a problem though, isn’t it?

It's a compiled system and the runtime is aware of the machine
architecture, including the cache size.

> Caches are all about speeding up repeated accesses to the same data.

No I don't think so.  Cache is fast memory.  If you write a value to
cache and then never access it again, that operation is still faster
than writing it to ram, or (worse) to disk.

[toc] | [prev] | [next] | [standalone]

#60906

On Sun, 14 Jun 2026 01:46:19 -0700, Paul Rubin
<no.email@nospam.invalid> wrote:

>Lawrence D’Oliveiro <ldo@nz.invalid> writes:
>>> CPU L2 cache, 256K or whatever.
>> That “or whatever” is a bit of a problem though, isn’t it?
>
>It's a compiled system and the runtime is aware of the machine
>architecture, including the cache size.
>
>> Caches are all about speeding up repeated accesses to the same data.
>
>No I don't think so.  Cache is fast memory.  If you write a value to
>cache and then never access it again, that operation is still faster
>than writing it to ram, or (worse) to disk.

But remember that when a (still valid) cache line is replaced, the
data must be pushed to a higher level of cache, and ultimately written
out to memory.  These mechinations use up memory system bandwidth that
might have gone to doing something else.

E.g., almost no runtime system bothers to invalidate the cache lines
belonging to freed stack frames.  Because of context switching, quite
a bit of cache bandwith can get taken up moving data that logically
has been abandoned.


I liked the idea of "backless memory" .. in-cache-only processing ...
promoted by the Mill.  No other architecture works that way and I was
sorry to see it fail.

[toc] | [prev] | [next] | [standalone]

#60909

George Neuner <gneuner2@comcast.net> writes:
> But remember that when a (still valid) cache line is replaced, the
> data must be pushed to a higher level of cache, and ultimately written
> out to memory.  These mechinations use up memory system bandwidth that
> might have gone to doing something else.

Yeah there seems to be no way to invalidate data cache without flushing
it.  Web search finds several people looking for ways to do it and it
just isn't there.  But, if you write a cached location, then overwrite
the location before the cache is flushed, the value you originally wrote
doesn't get written out.  Dunno if that helps.  It looks like ARM has a
mechanism for it, though the instructions are privileged:

https://developer.arm.com/documentation/den0042/0100/Caches/Invalidating-and-cleaning-cache-memory

I might sometime look into whether RISC-V has anything like that.

x86 ironically enough has a way to invalidate lines of the instruction
cache, but not the data cache.  You're supposed to use it if you write
self-modifying code.  Zomg.

In a semispace GC, I guess on the output side, you really do want to
push out the cached stuff you have written.  On the input side you could
potentially optimize by overlapping some cache loads using the x86
PREFETCHW instruction, but maybe the stuff you want is already in cache.

Anyway, that was for Haskell, which generates garbage by the bucketful.
I don't know if it's similar for Lisp.  Lawrence D. mentioned optimizing
Java programs by avoiding allocation, and I know that Lisp was like that
too, at least once upon a time.  Thus things like NCONC and NREVERSE,
the reviled LOOP macro destructively appending to lists, etc.  Scheme
tried to cultivate a more immutable style and I don't know what that
cost in GC overhead.

Someone mentioned observing GC using up to 30% of a Lisp program's cpu
cycles but usually not more.  That's consistent with what I've seen with
GHC.

[toc] | [prev] | [next] | [standalone]

#60853

Lawrence D´Oliveiro <ldo@nz.invalid> wrote:
> 
> 
> Whereas a garbage collector, by design, is spending much of its time
> hitting long-dead objects, which would likely have long since
> disappeared from the cache. That’s going to add an order of magnitude
> or two to your execution time -- which is why we have caches in the
> first place.
>

Um, that is not how copying GCs (which is almost certainly most modern
Lispoid GCs) work.  At all.

A naïve copying GC starts from some known roots and traces (and copies) all
objects reachable from those roots.  It never touches dead objects: once an
object is dead (has no references) it is never touched again by the GC.

The trick (one of the tricks) is then to arrange things so that programs
with very large amounts of live data do not result in the GC taking forever
and requiring a large amount of memory for the copy.  Hence generational
GCs.

Very old GCs, GCs which need to support languages with rigid ideas of where
objects are in memory, or GCs which need to be able to cope with tiny
available memory, may still do mark-and-sweep rather than copying.  This
(needing to support interfaces to primitive languages) is (I am pretty
sure) why LispWorks, say, still has a GC which can do mark and sweep for
some parts of memory.


-- 
www.tfeb.org/computer/

[toc] | [prev] | [next] | [standalone]

#60855

On Thu, 11 Jun 2026 17:42:08 -0000 (UTC), tfb wrote:

> A naïve copying GC starts from some known roots and traces (and
> copies) all objects reachable from those roots. It never touches
> dead objects: once an object is dead (has no references) it is never
> touched again by the GC.

That memory has to be marked as free for reallocation somehow. That
will be where the cache-thrashing comes in, no escaping it.

[toc] | [prev] | [next] | [standalone]

#60858

Lawrence D´Oliveiro <ldo@nz.invalid> wrote:
> 
> That memory has to be marked as free for reallocation somehow. That
> will be where the cache-thrashing comes in, no escaping it.
> 

It does not.  Once the live data has been copied from the area of memory it
is free, and new allocation may take place there.  You really need to think
about how a copying GC works.


-- 
www.tfeb.org/computer/

[toc] | [prev] | [next] | [standalone]

#60862

On Fri, 12 Jun 2026 12:34:26 -0000 (UTC), tfb wrote:

> Lawrence D´Oliveiro <ldo@nz.invalid> wrote:
>>
>> That memory has to be marked as free for reallocation somehow. That
>> will be where the cache-thrashing comes in, no escaping it.
>
> It does not. Once the live data has been copied from the area of
> memory it is free, and new allocation may take place there.

That’s even worse. That means the live objects have to be moved from
their existing locations, which might be in the cache, into new
locations which most likely are not.

[toc] | [prev] | [next] | [standalone]

#60867

On Sat, 13 Jun 2026 00:11:54 -0000 (UTC), Lawrence D´Oliveiro
<ldo@nz.invalid> wrote:

>On Fri, 12 Jun 2026 12:34:26 -0000 (UTC), tfb wrote:
>
>> Lawrence D´Oliveiro <ldo@nz.invalid> wrote:
>>>
>>> That memory has to be marked as free for reallocation somehow. That
>>> will be where the cache-thrashing comes in, no escaping it.
>>
>> It does not. Once the live data has been copied from the area of
>> memory it is free, and new allocation may take place there.
>
>That’s even worse. That means the live objects have to be moved from
>their existing locations, which might be in the cache, into new
>locations which most likely are not.

In most systems there are multiple caches backing one another. Typical
desktop now has 3 levels, and server CPUs have 5..8 levels. I think
you need to learn more about how multi-level caching works.


In multitasking systems it is pretty much guaranteed that a
(non-interrupt) context switch will result in losing everything the
switched-out thread had in 1st level cache.  By the time the thread
regains control, many context switches may have occurred and data in
2nd level and higher caches may be lost as well.

[Aside, context switching will trash the branch predictor tables as
well, so when a particular thread regains control, everything the
predictor knew about its branching behavior is gone and must be
relearned. This - more than anything else - is why switched in threads
are slow to begin.]


In hierarchical GC, the size of the "birthing" area where new
allocations are made typically is sized based on the 1st level cache.
It is very fast to collect because most new allocations die quickly,
and collecting leaves copies of many of the surviving objects still in
cache (at 2nd level if not 1st).

Also in threaded systems with hierarchical GC, often each thread has
its own private heap which can be collected by the thread itself
whenever necessary (ie. no context switch to a collector).

Copying GC also compacts the live set in the new location, which means
that fetches may bring multiple objects that are soon to be used.
E.g., copying collection can make discontiguous list nodes or array
elements contiguous in their new location.

[toc] | [prev] | [next] | [standalone]

#60876

George Neuner <gneuner2@comcast.net> writes:
> In hierarchical GC, the size of the "birthing" area where new
> allocations are made typically is sized based on the 1st level cache.
> It is very fast to collect because most new allocations die quickly,

Compilers can also do escape analysis and can often avoid
heap-allocating short-lived objects at all.  Plus they can often unbox
primitive-type values if the default representation is boxed.

I'm pretty sure CPython has never attempted something like that.  No
idea about PyPy or other implementations.  Python was traditionally a
scripting wrapper around a bunch of C libraries, with pure interpreter
performance not being that important in its own right.  Of course it has
gradually become more important and gotten more attention.

[toc] | [prev] | [next] | [standalone]

#60878

Paul Rubin <no.email@nospam.invalid> wrote or quoted:
>Compilers can also do escape analysis and can often avoid
>heap-allocating short-lived objects at all.  Plus they can often unbox
>primitive-type values if the default representation is boxed.
>
>I'm pretty sure CPython has never attempted something like that.  No
>idea about PyPy or other implementations.  Python was traditionally a
>scripting wrapper around a bunch of C libraries, with pure interpreter
>performance not being that important in its own right.  Of course it has
>gradually become more important and gotten more attention.

  Well, what Python does have with regard to unboxing are array
  classes that store values unboxed. But this is more for memory
  efficiency.

  FWIW:

  CPython 3.15 is about 60 percent faster than CPython 3.10. 
  In the list of modifications below, only "Immortal Objects"
  seems to be directly related to garbage collection though.

| Python 3.11
| 
| Specializing Adaptive Interpreter   Optimizes execution by dynamically
| replacing generic bytecodes with type-specific opcodes for repetitive
| tasks.
| 
| Faster Startup   Caches code objects inside Frozen imports to skip
| standard module initialization overhead.
| 
| Cheaper Stack Frames   Minimizes memory usage and layout sizes for
| Python frame allocations.
| 
| Inlined Function Calls   Bypasses the traditional C stack overhead
| during basic internal Python function calls.
| 
| Zero-Cost Exceptions   Allocates zero runtime performance overhead to
| code executing within a try block when no exception occurs.
| 
| Python 3.12
| 
| Comprehension Inlining   List, dict, and set comprehensions are
| compiled directly inline, eliminating single-use function object
| creation overhead.
| 
| Per-Interpreter GIL   Enables isolated execution across
| sub-interpreters by equipping each with a unique Global Interpreter
| Lock (GIL).
| 
| Immortal Objects   Skips reference-count modifications for global,
| persistent runtime entities.
| 
| Eager Async Tasks   Adds asyncio.eager_task_factory() to conditionally
| bypass event-loop scheduling for a 2x to 5x performance boost.
| 
| Fast Protocol Checks   Accelerates standard isinstance() evaluations
| against runtime-checkable protocols by up to 20 times.
| 
| Python 3.13
| 
| Experimental Free-Threaded Build   Offers a specialized configuration
| to run Python with the GIL completely disabled for parallel multi-core
| scaling.
| 
| Copy-and-Patch JIT   Introduces an experimental Just-In-Time (JIT)
| compiler framework to establish future native code compilation
| pathways.
| 
| Mimalloc Integration   Adds Microsoft's high-performance memory
| allocator to optimize internal runtime threads.
| 
| Stripped Docstrings   Discards excessive indentation space within
| runtime docstrings to reduce overall .pyc memory footings.
| 
| Python 3.14
| 
| Tail-Call Interpreter   Implements a dedicated tail-call configuration
| using modern compilers to deliver 3-5% base speedups across execution
| frames.
| 
| Deferred Annotations   Postpones active evaluation of standard type
| hints until explicit runtime inspection is initiated.
| 
| Zero-Overhead Debugging   Adds a native external execution protocol to
| hook profilers without causing standard runtime delay.
| 
| Python 3.15
| 
| Lazy Imports Built-in   Provides native PEP 810 lazy imports to
| optimize initial startup speeds across heavy applications.
| 
| Tachyon High-Frequency Profiler   Features a highly optimized,
| zero-overhead statistical sampling profiler ready for active
| production instances.
| 
| Native Frame Pointers   Enables native architecture frame pointers by
| default to speed up eBPF tools and system tracing.
| 
| Upgraded JIT Pipeline   Substantially enhances the core assembly of
| the experimental JIT compilation tier.

[toc] | [prev] | [next] | [standalone]

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6  Next page →

Back to top | Article view | comp.lang.lisp

csiph-web