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

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