On Sat, Jul 16, 2022 at 08:59:57PM -0700, Nathan Bossart wrote: > On Fri, Jul 15, 2022 at 01:08:57PM -0700, Andres Freund wrote: >> I wonder if we additionally / alternatively could use a faster method of >> searching the array linearly, e.g. using SIMD. > > I looked into using SIMD. The patch is attached, but it is only intended > for benchmarking purposes and isn't anywhere close to being worth serious > review. There may be a simpler/better way to implement the linear search, > but this seemed to work well. Overall, SIMD provided a decent improvement. > I had to increase the number of writers quite a bit in order to demonstrate > where the hash tables began winning. Here are the numbers: > > writers head simd hash > 256 663 632 694 > 512 530 618 637 > 768 489 544 573 > 1024 364 508 562 > 2048 185 306 485 > 4096 146 197 441 > > While it is unsurprising that the hash tables perform the best, there are a > couple of advantages to SIMD that might make that approach worth > considering. For one, there's really no overhead (i.e., you don't need to > sort the array or build a hash table), so we can avoid picking an arbitrary > threshold and just have one code path. Also, a SIMD implementation for a > linear search through an array of integers could likely be easily reused > elsewhere.
>From the discussion thus far, it seems there is interest in optimizing [sub]xip lookups, so I'd like to spend some time moving it forward. I think the biggest open question is which approach to take. Both the SIMD and hash table approaches seem viable, but I think I prefer the SIMD approach at the moment (see the last paragraph of quoted text for the reasons). What do folks think? -- Nathan Bossart Amazon Web Services: https://aws.amazon.com
