From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via "Emacs development discussions." Newsgroups: gmane.emacs.devel Subject: Re: [GNU ELPA] New package: tam Date: Wed, 20 Sep 2023 13:30:34 -0400 Message-ID: References: <87a5tjyg83.fsf@posteo.net> <87led39zyn.fsf@posteo.net> <87pm2d8d2w.fsf@posteo.net> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="11551"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) To: emacs-devel@gnu.org Cancel-Lock: sha1:EZkIlBomyMpS12rK3CYsNMc7FXY= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Sep 20 19:33:17 2023 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1qj14e-0002lf-IH for ged-emacs-devel@m.gmane-mx.org; Wed, 20 Sep 2023 19:33:16 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qj13e-00024l-Jg; Wed, 20 Sep 2023 13:32:14 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qj13c-00024C-1q for emacs-devel@gnu.org; Wed, 20 Sep 2023 13:32:12 -0400 Original-Received: from ciao.gmane.io ([116.202.254.214]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qj13W-0000yf-H7 for emacs-devel@gnu.org; Wed, 20 Sep 2023 13:32:11 -0400 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1qj13T-0001C2-MN for emacs-devel@gnu.org; Wed, 20 Sep 2023 19:32:03 +0200 X-Injected-Via-Gmane: http://gmane.org/ Received-SPF: pass client-ip=116.202.254.214; envelope-from=ged-emacs-devel@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: -16 X-Spam_score: -1.7 X-Spam_bar: - X-Spam_report: (-1.7 / 5.0 requ) BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.249, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:310846 Archived-At: >> Re your last change in [0], why use records directly instead of having >> the code being generated via cl-defstruct? The commit messages doesn't >> really explain your reasoning to me. > The library is supposed to provide alloc/free functions that run in > O(1) time to the extent that is possible for emacs-lisp code, for use > in process sentinels and similar situations. I took a look at the > byte-code generated for those two functions when using the > cl-defstruct definitions, and the accessors and setters were > not inlined. That's odd. Could you give more details about what&how you checked that? > Aside from the unknown complexity of invoking those functions, every > call has a risk of overflowing the current stack and requiring an > additional stack segment be allocated. That would still be O(1) in my book. > Accumulating a list in the right order is only O(n^2) if you only keep > the head of the list. The queue structure (or what I would write with > let-bound variables) holds a reference to the last cons cell of the > list to use in adding an entry on the end. It's probably negligible > for very short lists, but it's just bad form. Using `push`es followed by `nreverse` is usually more efficient than either of those. It's a standard idiom in Lisp for good reasons. If you care about the constant of your O(1) above, I recommend you use `nreverse` here as well :-) Stefan