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

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