From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Helmut Eller Newsgroups: gmane.emacs.devel Subject: Re: Markers in a gap array Date: Wed, 17 Jul 2024 18:48:07 +0200 Message-ID: <87v81455iw.fsf@gmail.com> References: <87ikxlqwu6.fsf@localhost> <87le2hp6ug.fsf@localhost> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2599"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Pip Cet , Ihor Radchenko , emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Jul 17 18:49:37 2024 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 1sU7qR-0000Ql-AC for ged-emacs-devel@m.gmane-mx.org; Wed, 17 Jul 2024 18:49:35 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sU7pA-0005zm-V5; Wed, 17 Jul 2024 12:48:18 -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 1sU7p9-0005zY-GY for emacs-devel@gnu.org; Wed, 17 Jul 2024 12:48:15 -0400 Original-Received: from mail-ej1-x62e.google.com ([2a00:1450:4864:20::62e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sU7p5-0002Fy-G9 for emacs-devel@gnu.org; Wed, 17 Jul 2024 12:48:15 -0400 Original-Received: by mail-ej1-x62e.google.com with SMTP id a640c23a62f3a-a77c4309fc8so824350166b.3 for ; Wed, 17 Jul 2024 09:48:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721234889; x=1721839689; darn=gnu.org; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to; bh=y+8PenIWj1MJV9eXlJ9YuRnSnNJg/NIXK/ySXpUeyxk=; b=a4xevibF7YtgWth1T8adrx1K6uNiqZxsBDAPyOtPdlhN+1nenCW+ZIlaQZQU84tSxk DUCpYVccJhpljACpfMOigmpLm2R7XtDJ59BQ5S/OOlYqRo2gRMEf8FE3P5zxJi704M93 CDG2m0ak7YaGaluMoiJndRdBRA2zI27UtbaW0uI7j4qBDbWV2HLqqCoycLgRD6QM03Ox wt0KrGgnUs/x0UvE++ZYB3utBuSKbch7pYD8dzyIFM4wyyPPUxsNzFk+t42qeNRdkThK 1eJPjYo6zeGnXES9DpzGD+wdBwXqATEdFyUDdqs0iCeb0haKG3OhD7esLNvoD4iGECHX BmDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721234889; x=1721839689; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=y+8PenIWj1MJV9eXlJ9YuRnSnNJg/NIXK/ySXpUeyxk=; b=X/tttZdN1i85Nwb758L2SKLv+SpItKiU0mb+0bu9oxnV1LUllG/dLyCuYj+hcn0WeQ TNTUdXkv/ztHBWsXqXdmJkNiLPcReQeggxtXkw5V8quTCVedZq1NhPMpg8v3RJ223Hwz 2drQs+PI/A0VGf668xtUoxngxFomaElKrAL9wdSWdoMXUKrCsE/7sergLq/Yj6wlRJIV Zq9tyv9AYYiP2UqowX4N980yGyW2mRA+Gh433q/zqU92hbJZQO1J0cUa/yfrMoIfJFLG /XFpJtv/gCMpqCFtnsn6HJrsjCHo6BzdSW2zh9uCp5U4h/GwF5VHbjMx7gjOgwWBNABE I7OA== X-Forwarded-Encrypted: i=1; AJvYcCVDO4j/LeaIZuzr8pJu707FcyvW7B4M3qgF/EB+EVQ0SZ+wMnghJC+8LT/q8ytvtC9VWud0XOBworXEgmWVBzGPpaiB X-Gm-Message-State: AOJu0YypFP3DTKohx/y4k1RA+MOE+vfHgUVxRdAazIO3zZlmBkVSsRvN zZRtPKTvzwa6LFhDw2HoOtiW4lLcrlO1HC5EIrLGMbSdUfBhWa3+MmFrKw== X-Google-Smtp-Source: AGHT+IF1BYbvXiljeSQYcIiUguAsadK/9PXFX9HgRb2FxAnz3qQ2BMkyfLmN6VqxyFXxFEBkVQZIPg== X-Received: by 2002:a17:906:741:b0:a6f:1c81:e220 with SMTP id a640c23a62f3a-a7a01120bf2mr170776966b.13.1721234888298; Wed, 17 Jul 2024 09:48:08 -0700 (PDT) Original-Received: from caladan (dialin-234199.rol.raiffeisen.net. [195.254.234.199]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a79bc80101fsm474008666b.179.2024.07.17.09.48.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 17 Jul 2024 09:48:07 -0700 (PDT) In-Reply-To: (Stefan Monnier's message of "Thu, 04 Jul 2024 16:42:41 -0400") Received-SPF: pass client-ip=2a00:1450:4864:20::62e; envelope-from=eller.helmut@gmail.com; helo=mail-ej1-x62e.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham 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:321759 Archived-At: On Thu, Jul 04 2024, Stefan Monnier wrote: >> Could you share a more complete recipe for the benchmark? I wonder how it >> compares to Gerd's weak vector/freelist in scratch/igc. > > Put it into the `benchmark` subdir of `elisp-benchmarks` and then do > > emacs --batch -Q -l .../elisp-benchmarks/elisp-benchmarks-autoloads.el \ > --eval '(elisp-benchmarks-run "bytechar")' > The current scratch/igc branch, configured with MPS and -O2 -fno-omit-frame-pointer: | test || tot avg (s) | tot avg err (s) | |------------------------++-------------+-----------------| | bytechar || 12.11 | 0.18 | | bytechar-100k || 12.38 | 0.17 | | bytechar-100k-nolookup || 9.14 | 0.22 | | bytechar-100k-random || 271.52 | 14.27 | | bytechar-100k-rev || 12.38 | 0.24 | | bytechar-10k-random || 38.08 | 1.43 | | bytechar-1k-random || 14.95 | 0.48 | | bytechar-nolookup || 8.97 | 0.12 | |------------------------++-------------+-----------------| | total || 379.53 | 14.36 | and without MPS: | test || tot avg (s) | tot avg err (s) | |------------------------++-------------+-----------------| | bytechar || 11.42 | 0.03 | | bytechar-100k || 11.48 | 0.02 | | bytechar-100k-nolookup || 9.15 | 0.00 | | bytechar-100k-random || 16.39 | 0.02 | | bytechar-100k-rev || 11.48 | 0.02 | | bytechar-10k-random || 11.97 | 0.02 | | bytechar-1k-random || 11.56 | 0.01 | | bytechar-nolookup || 9.13 | 0.04 | |------------------------++-------------+-----------------| | total || 92.58 | 0.06 | So the weak vector doesn't compare very well to the linked list. Maybe because the vector only grows and never shrinks. The idea with the sorted markers in a gap array would probably avoid the worst of this. I wonder why the linked list doesn't seem similar issues.