Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ob42Q-0006Ms-0o for pgsql-hackers@arkaria.postgresql.org; Wed, 21 Sep 2022 18:01:34 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1ob42O-0001gW-VN for pgsql-hackers@arkaria.postgresql.org; Wed, 21 Sep 2022 18:01:32 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ob42O-0001gN-KC for pgsql-hackers@lists.postgresql.org; Wed, 21 Sep 2022 18:01:32 +0000 Received: from mail-pg1-x529.google.com ([2607:f8b0:4864:20::529]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1ob42M-0004TB-Ah for pgsql-hackers@postgresql.org; Wed, 21 Sep 2022 18:01:31 +0000 Received: by mail-pg1-x529.google.com with SMTP id f193so6736699pgc.0 for ; Wed, 21 Sep 2022 11:01:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date; bh=trCGHCdV9K9yxGHAVor7zVSONnlipf9XmwgYZokuc0c=; b=FtttleKsmBuY8/i/75Y2eSq2w2WTdiL4PskUf2dKWz6agZftVgpyOzeub0pZq3w2pA F/3AiNu9jbtNZoZe1aY8lIGskuvQOmAlUdAYzr9vvye8cr993gzM1LqruXhbHnhMYSJH RnO5ckCwIRgR5luhnboSdnCW8mqEMDAQN8R/rW2F1CIVLH/BUK2HKvra6uIRgeVm7XYZ mtmJ6llGJjl4Xwe89PzgW7wnv511B9nWCGF/JWumJwkjbMWq3eNg6DBwwAdF3kdcqC1F rUQ0zZaoxAjlzkHvlvrLmMpatWgW/T+vrsITf3ksWQeLRZj17DtAYEXbWD8umhU/7E9o gKbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date; bh=trCGHCdV9K9yxGHAVor7zVSONnlipf9XmwgYZokuc0c=; b=QqAo0UlwiOYmsFlsyKb9rl3EhAtT28NCT9dYed0GF39vNh0qJEqmEM2ovh1uZnO6wj WZmraG42RDC+tngy7KuNbwIrfGEcPERwXd0e2ztx5te+L1QUq8CaC/zAZvRISmp333PG g9U50XFv47xmVdDkRScMBxUlHYIG9+g8eOF8f0+jkqJwBDkigypwM8Lk5aGA1abXsS5u HI4ZdTCxo+/6m10QahBx3S+XFuBMmesO5n236YTX8+6kANhDu5ckW6Lt4Jx1NcgFrex3 vdG9dPQ8NBQtHq3oyuDimEQsojHrKKkNOaoUJUyrdFKSjN4RIyXUvUpD5J/k57t+r6vG 4VUg== X-Gm-Message-State: ACrzQf3EiMuJuOXCUagWP/dEb/t6Gq5nJD4Z3fb7Swhz2IcLa4PJltar nwTkkNJnSErRogf533cdUxM= X-Google-Smtp-Source: AMsMyM7p6QbOF4srdr5rXCNPojz5z56JNGqN9gnWMLnoY+vEUy6dRnCNp6PD/FsYB0DXF0E+btKoeA== X-Received: by 2002:a63:5853:0:b0:43b:e67b:969a with SMTP id i19-20020a635853000000b0043be67b969amr4210529pgm.354.1663783289027; Wed, 21 Sep 2022 11:01:29 -0700 (PDT) Received: from nathanxps13 ([50.47.162.83]) by smtp.gmail.com with ESMTPSA id e2-20020a631e02000000b0042b5b036da4sm2132305pge.68.2022.09.21.11.01.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 21 Sep 2022 11:01:28 -0700 (PDT) Date: Wed, 21 Sep 2022 11:01:26 -0700 From: Nathan Bossart To: John Naylor Cc: Masahiko Sawada , Andres Freund , Matthias van de Meent , Yura Sokolov , PostgreSQL-development Subject: Re: [PoC] Improve dead tuple storage for lazy vacuum Message-ID: <20220921180126.GA453160@nathanxps13> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk On Wed, Sep 21, 2022 at 01:17:21PM +0700, John Naylor wrote: > In trying to wrap the SIMD code behind layers of abstraction, the latest > patch (and Nathan's cleanup) threw it away in almost all cases. To explain, > we need to talk about how vectorized code deals with the "tail" that is too > small for the register: > > 1. Use a one-by-one algorithm, like we do for the pg_lfind* variants. > 2. Read some junk into the register and mask off false positives from the > result. > > There are advantages to both depending on the situation. > > Patch v5 and earlier used #2. Patch v6 used #1, so if a node16 has 15 > elements or less, it will iterate over them one-by-one exactly like a > node4. Only when full with 16 will the vector path be taken. When another > entry is added, the elements are copied to the next bigger node, so there's > a *small* window where it's fast. > > In short, this code needs to be lower level so that we still have full > control while being portable. I will work on this, and also the related > code for node dispatch. Is it possible to use approach #2 here, too? AFAICT space is allocated for all of the chunks, so there wouldn't be any danger in searching all them and discarding any results >= node->count. Granted, we're depending on the number of chunks always being a multiple of elements-per-vector in order to avoid the tail path, but that seems like a reasonably safe assumption that can be covered with comments. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com