Re: [Sbcl-bugs] [BUG] FORMAT tokenize-control-string cache too small (128 entries, thrashes in large applications)

Huge RAM? In this economy?

On Wed, Mar 11, 2026 at 6:57 PM John Mallery <[email protected]> wrote:
>
> What do you make of this in the era huge ram?
>
> > On Mar 11, 2026, at 16:51, Stas Boukarev <[email protected]> wrote:
> >
> > Larger caches are not free. And your 8KB math is only for the vector
> > holding strings, not the strings themselves.
> >
> > On Wed, Mar 11, 2026 at 6:50 PM John C Mallery <[email protected]> wrote:
> >>
> >> Well, this is not an argument to avoid making the format cache larger.
> >>
> >>> On Mar 11, 2026, at 16:47, Stas Boukarev <[email protected]> wrote:
> >>>
> >>> But if you are after performance why are you calling format with
> >>> unknown strings. Maybe use FORMATTER?
> >>>
> >>> On Wed, Mar 11, 2026 at 6:45 PM John C Mallery <[email protected]> wrote:
> >>>>
> >>>> I don’t know about SBCL, but we have a fast-format function which does exactly that.  We don’t handle, however, complex directives.  In any case, this bug in SBCL is fixed by using a large hash table to cache the string.
> >>>>
> >>>>> On Mar 11, 2026, at 16:27, Stas Boukarev <[email protected]> wrote:
> >>>>>
> >>>>> But why are these format strings not processed at compile time?
> >>>>>
> >>>>>
> >>>>> On Wed, Mar 11, 2026 at 6:22 PM John C Mallery <[email protected]> wrote:
> >>>>>>
> >>>>>> SBCL version: 2.6.1 (also affects current git HEAD)
> >>>>>> Platform: all
> >>>>>>
> >>>>>> DESCRIPTION
> >>>>>>
> >>>>>> The FORMAT control string tokenizer cache (tokenize-control-string)
> >>>>>> uses :hash-bits 7, giving a 128-entry 2-way set-associative cache.
> >>>>>> In large applications with many distinct format strings, the cache
> >>>>>> fills completely and thrashes -- every collision re-tokenizes the
> >>>>>> control string, allocating fresh tokenized representations.
> >>>>>>
> >>>>>> In CL-HTTP (a web server with ~200 distinct format strings in its
> >>>>>> codebase), the cache is 128/128 full.  Profiling under load shows
> >>>>>> tokenize-control-string accounting for 7.0% of all allocation during
> >>>>>> HTTP request serving (~28K req/s).
> >>>>>>
> >>>>>> HOW TO REPRODUCE
> >>>>>>
> >>>>>> ;; Create enough distinct format strings to fill the 128-entry cache
> >>>>>> (let ((strings (loop for i below 200
> >>>>>>                    collect (format nil "test-~D: ~~A ~~D" i))))
> >>>>>> ;; Warm the cache
> >>>>>> (dolist (s strings) (format nil s "x" 1))
> >>>>>> ;; Measure -- cache is now thrashing
> >>>>>> (let ((before (sb-ext:get-bytes-consed)))
> >>>>>>   (dotimes (j 100)
> >>>>>>     (dolist (s strings)
> >>>>>>       (format nil s "x" 1)))
> >>>>>>   (format t "~,1F bytes/format call~%"
> >>>>>>           (/ (float (- (sb-ext:get-bytes-consed) before))
> >>>>>>              (* 100.0 (length strings))))))
> >>>>>>
> >>>>>> ;; With :hash-bits 7 (128 entries): ~200+ bytes/call (re-tokenizing)
> >>>>>> ;; With :hash-bits 10 (1024 entries): ~0 bytes/call (cache hits)
> >>>>>>
> >>>>>> FIX
> >>>>>>
> >>>>>> 1-line change in src/code/format.lisp.  Increase :hash-bits from 7
> >>>>>> to 10 (1024 entries instead of 128):
> >>>>>>
> >>>>>> --- a/src/code/format.lisp
> >>>>>> +++ b/src/code/format.lisp
> >>>>>> @@ -23,7 +23,7 @@
> >>>>>> #-sb-xc-host
> >>>>>> (defun-cached (tokenize-control-string
> >>>>>>             :memoizer memoize
> >>>>>> -               :hash-bits 7
> >>>>>> +               :hash-bits 10
> >>>>>>             :hash-function (lambda (string)
> >>>>>>                              (ash (get-lisp-obj-address string)
> >>>>>>                                   #.(- sb-vm:n-lowtag-bits))))
> >>>>>>
> >>>>>> COST
> >>>>>>
> >>>>>> The cache vector grows from 128 to 1024 entries (simple-vector).
> >>>>>> On 64-bit, this is ~8KB of memory -- negligible for any application
> >>>>>> large enough to have 128+ distinct format strings.  The cache is
> >>>>>> allocated lazily on first use, so small programs pay nothing.
> >>>>>>
> >>>>>> The defun-cached assert already allows hash-bits up to 12:
> >>>>>> (assert (typep hash-bits '(integer 5 12)))
> >>>>>>
> >>>>>> IMPACT
> >>>>>>
> >>>>>> Any application with more than ~64 active format strings (the
> >>>>>> effective capacity of a 128-entry 2-way cache) will see thrashing.
> >>>>>> Web servers, GUI applications, and compilers commonly exceed this.
> >>>>>>
> >>>>>>
> >>>>>> _______________________________________________
> >>>>>> Sbcl-bugs mailing list
> >>>>>> [email protected]
> >>>>>> https://lists.sourceforge.net/lists/listinfo/sbcl-bugs
> >>>>
> >>
>


_______________________________________________
Sbcl-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/sbcl-devel