From unknown Wed Jun 18 23:17:44 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#16358 <16358@debbugs.gnu.org> To: bug#16358 <16358@debbugs.gnu.org> Subject: Status: combinatorial explosion in elided stack trace Reply-To: bug#16358 <16358@debbugs.gnu.org> Date: Thu, 19 Jun 2025 06:17:44 +0000 retitle 16358 combinatorial explosion in elided stack trace reassign 16358 guile submitter 16358 Zefram severity 16358 normal thanks From debbugs-submit-bounces@debbugs.gnu.org Sun Jan 05 18:44:22 2014 Received: (at submit) by debbugs.gnu.org; 5 Jan 2014 23:44:22 +0000 Received: from localhost ([127.0.0.1]:37201 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VzxMj-0004yt-VV for submit@debbugs.gnu.org; Sun, 05 Jan 2014 18:44:22 -0500 Received: from eggs.gnu.org ([208.118.235.92]:45466) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Vzwim-0003op-9U for submit@debbugs.gnu.org; Sun, 05 Jan 2014 18:03:04 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Vzwid-0001h4-M9 for submit@debbugs.gnu.org; Sun, 05 Jan 2014 18:03:04 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:35512) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Vzwid-0001h0-J1 for submit@debbugs.gnu.org; Sun, 05 Jan 2014 18:02:55 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:47162) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VzwiX-0004Oj-9P for bug-guile@gnu.org; Sun, 05 Jan 2014 18:02:55 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VzwiR-0001gS-A4 for bug-guile@gnu.org; Sun, 05 Jan 2014 18:02:49 -0500 Received: from river.fysh.org ([5.135.154.127]:53130) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VzwiR-0001gN-46 for bug-guile@gnu.org; Sun, 05 Jan 2014 18:02:43 -0500 Received: from zefram by river.fysh.org with local (Exim 4.80 #2 (Debian)) id 1VzwiM-0000HF-9D; Sun, 05 Jan 2014 23:02:38 +0000 Date: Sun, 5 Jan 2014 23:02:38 +0000 From: Zefram To: bug-guile@gnu.org Subject: combinatorial explosion in elided stack trace Message-ID: <20140105230238.GC30283@fysh.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Sun, 05 Jan 2014 18:44:19 -0500 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) In guile 2.0.9, if an error is signalled in the interpreter, and the stack contains in a certain position an object whose unabbreviated print representation is very large, then the process of displaying the stack trace will take a huge amount of time and memory, pausing in the middle of output, even though the displayed stack trace doesn't actually show the object at all. Test case: $ cat t6 (define bs (let aaa ((n 100) (v '())) (if (= n 0) v (aaa (- n 1) (cons v v))))) (write (list bs (error "wibble"))) $ guile-2.0 --no-auto-compile t6 Backtrace: In ice-9/boot-9.scm: 157: 11 [catch #t # ...] In unknown file: ?: 10 [apply-smob/1 #] In ice-9/boot-9.scm: 63: 9 [call-with-prompt prompt0 ...] In ice-9/eval.scm: 432: 8 [eval # #] In ice-9/boot-9.scm: 2320: 7 [save-module-excursion #] 3968: 6 [#] 1645: 5 [%start-stack load-stack #] 1650: 4 [#] In unknown file: ?: 3 [primitive-load "/home/zefram/usr/guile/t6"] In ice-9/eval.scm: 387: 2 ^Z zsh: suspended guile-2.0 --no-auto-compile t6 $ jobs -l [1] + 32574 suspended guile-2.0 --no-auto-compile t6 $ ps vw 32574 PID TTY STAT TIME MAJFL TRS DRS RSS %MEM COMMAND 32574 pts/5 T 0:36 0 3 2266300 1634556 9.9 guile-2.0 --no-auto-compile t6 With the test's size parameter at 100 as above, there is no realistic prospect of actually completing generation of the stack trace. For some range of values (about 25 on my machine) there will be a noticeable pause, after which the stack trace completes: ... 387: 2 [eval # ()] 387: 1 [eval # ()] In unknown file: ?: 0 [scm-error misc-error #f "~A" ("wibble") #f] It appears that it's generating the entire print representation of the object behind the scenes, though it then obviously throws it away. Experimentation with customising print methods for SRFI-9 record types shows that the delay and memory usage depend on the print representation per se, rather than on the amount of structure beneath the object. (A record-based cons-like type produces similar behaviour to the cons test when using the default print method that shows the content. Replacing it with a print method that emits a fixed string and doesn't recurse eliminates the delay entirely.) If my test program is run in compiled form (via auto-compilation) then it doesn't exhibit the pause. Actually it gets optimised such that the problem object isn't anywhere near what the stack trace displays, so for a fair test the program needs to be tweaked. It can be arranged for the problem object to be directly mentioned in the stack trace, and there is still no pause: the object appears in a highly abbreviated form, such as 2: 1 [vv ((# # # # ...) (# # # # ...) (# # # # ...) (# # # # ...) ...)] For comparison, guile-1.8 never exhibits this problem. By default it doesn't emit a stack trace for a script, but it can be asked to do so via --debug. It then behaves like the compiled form of guile-2.0: there is no delay, and the object is shown in very abbreviated form. Debian incarnation of this bug report: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=734132 -zefram From debbugs-submit-bounces@debbugs.gnu.org Tue Jun 21 08:28:53 2016 Received: (at 16358-done) by debbugs.gnu.org; 21 Jun 2016 12:28:53 +0000 Received: from localhost ([127.0.0.1]:48708 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bFKnV-00021L-J6 for submit@debbugs.gnu.org; Tue, 21 Jun 2016 08:28:53 -0400 Received: from pb-sasl1.pobox.com ([64.147.108.66]:57340 helo=sasl.smtp.pobox.com) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bFKnT-00021D-5q for 16358-done@debbugs.gnu.org; Tue, 21 Jun 2016 08:28:51 -0400 Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by pb-sasl1.pobox.com (Postfix) with ESMTP id DB10A229BF; Tue, 21 Jun 2016 08:28:46 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; s=sasl; bh=c4x5VpikucAzgMAQ/hQLJTfCg6I=; b=iOxwb6 2FJw4IAkICj99fvzHlBV5XxrLtpr7LSK7JuaXx6kpD1Vk0dxG5fOJfN4Jh8qQCgf do5O8dMLwgBWmEv6su7ofL9qRVQ3L/uzAiJcjAQy6v0mESUql0BHJq+f2T4NAzIs Hj2L4mnb/12rVlS38oinaQFjUDwN0+FaoDabw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=sasl; b=aYwXUU8rs9wFcvackR6WPURcsworYQAP w7ZkFyx2JoGKnaZPKHCSgZV4wAKcPdYRX6TkD4xNt3HHQ6P7Zg6DJUSgL8Cjb29q uxXnTfqw6Rugs0UbrnVlnLLLza+17odQrI/rPqUWCj0TpaxZ7//FfXGkwi5gyHs2 SelUpK/4gYE= Received: from pb-sasl1.nyi.icgroup.com (unknown [127.0.0.1]) by pb-sasl1.pobox.com (Postfix) with ESMTP id C216F229BD; Tue, 21 Jun 2016 08:28:46 -0400 (EDT) Received: from clucks (unknown [88.160.190.192]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by pb-sasl1.pobox.com (Postfix) with ESMTPSA id D31DA229BC; Tue, 21 Jun 2016 08:28:45 -0400 (EDT) From: Andy Wingo To: Zefram Subject: Re: bug#16358: combinatorial explosion in elided stack trace References: <20140105230238.GC30283@fysh.org> Date: Tue, 21 Jun 2016 14:28:38 +0200 In-Reply-To: <20140105230238.GC30283@fysh.org> (zefram@fysh.org's message of "Sun, 5 Jan 2014 23:02:38 +0000") Message-ID: <87vb12zpxl.fsf@pobox.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Pobox-Relay-ID: B2D8C2E6-37AB-11E6-974E-C1836462E9F6-02397024!pb-sasl1.pobox.com X-Spam-Score: -1.4 (-) X-Debbugs-Envelope-To: 16358-done Cc: 16358-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.4 (-) Hi Zefram, Thanks for the great report! I believe this is fixed in v2.1.3. Reproducing the bug is a little different there but I think I did get it so that Guile should try to print out the value. I don't know if we would be able to fix this in 2.0 though :/ I am closing because I believe it to be fixed, albeit in the next release series. Regards, Andy On Mon 06 Jan 2014 00:02, Zefram writes: > In guile 2.0.9, if an error is signalled in the interpreter, and the > stack contains in a certain position an object whose unabbreviated print > representation is very large, then the process of displaying the stack > trace will take a huge amount of time and memory, pausing in the middle > of output, even though the displayed stack trace doesn't actually show > the object at all. Test case: > > $ cat t6 > (define bs (let aaa ((n 100) (v '())) (if (= n 0) v (aaa (- n 1) (cons v v))))) > (write (list bs (error "wibble"))) > $ guile-2.0 --no-auto-compile t6 > Backtrace: > In ice-9/boot-9.scm: > 157: 11 [catch #t # ...] > In unknown file: > ?: 10 [apply-smob/1 #] > In ice-9/boot-9.scm: > 63: 9 [call-with-prompt prompt0 ...] > In ice-9/eval.scm: > 432: 8 [eval # #] > In ice-9/boot-9.scm: > 2320: 7 [save-module-excursion #] > 3968: 6 [#] > 1645: 5 [%start-stack load-stack #] > 1650: 4 [#] > In unknown file: > ?: 3 [primitive-load "/home/zefram/usr/guile/t6"] > In ice-9/eval.scm: > 387: 2 ^Z > zsh: suspended guile-2.0 --no-auto-compile t6 > $ jobs -l > [1] + 32574 suspended guile-2.0 --no-auto-compile t6 > $ ps vw 32574 > PID TTY STAT TIME MAJFL TRS DRS RSS %MEM COMMAND > 32574 pts/5 T 0:36 0 3 2266300 1634556 9.9 guile-2.0 --no-auto-compile t6 > > With the test's size parameter at 100 as above, there is no realistic > prospect of actually completing generation of the stack trace. For some > range of values (about 25 on my machine) there will be a noticeable pause, > after which the stack trace completes: > > ... > 387: 2 [eval # ()] > 387: 1 [eval # ()] > In unknown file: > ?: 0 [scm-error misc-error #f "~A" ("wibble") #f] > > It appears that it's generating the entire print representation of > the object behind the scenes, though it then obviously throws it away. > Experimentation with customising print methods for SRFI-9 record types > shows that the delay and memory usage depend on the print representation > per se, rather than on the amount of structure beneath the object. > (A record-based cons-like type produces similar behaviour to the > cons test when using the default print method that shows the content. > Replacing it with a print method that emits a fixed string and doesn't > recurse eliminates the delay entirely.) > > If my test program is run in compiled form (via auto-compilation) then > it doesn't exhibit the pause. Actually it gets optimised such that the > problem object isn't anywhere near what the stack trace displays, so for > a fair test the program needs to be tweaked. It can be arranged for the > problem object to be directly mentioned in the stack trace, and there is > still no pause: the object appears in a highly abbreviated form, such as > > 2: 1 [vv ((# # # # ...) (# # # # ...) (# # # # ...) (# # # # ...) ...)] > > For comparison, guile-1.8 never exhibits this problem. By default > it doesn't emit a stack trace for a script, but it can be asked to do > so via --debug. It then behaves like the compiled form of guile-2.0: > there is no delay, and the object is shown in very abbreviated form. > > Debian incarnation of this bug report: > http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=734132 > > -zefram From unknown Wed Jun 18 23:17:44 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Wed, 20 Jul 2016 11:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator