On Thu, Jan 30, 2025 at 12:17:51AM +0100, Andreas Gruenbacher wrote:
> On Wed, Jan 29, 2025 at 10:30 PM Kent Overstreet
> <kent.overstreet@xxxxxxxxx> wrote:
> > On Wed, Jan 29, 2025 at 10:21:31PM +0100, Andreas Gruenbacher wrote:
> > > On Wed, Jan 29, 2025 at 9:28 PM Kent Overstreet
> > > <kent.overstreet@xxxxxxxxx> wrote:
> > > > On Wed, Jan 29, 2025 at 07:21:49PM +0100, Andreas Gruenbacher wrote:
> > > > > On Wed, Jan 29, 2025 at 7:04 PM Kent Overstreet
> > > > > <kent.overstreet@xxxxxxxxx> wrote:
> > > > > > On Tue, Jan 28, 2025 at 05:38:48PM +0100, Andreas Gruenbacher wrote:
> > > > > > > Rename eytzinger0_find_test_val() to eytzinger0_find_test_le() and add a
> > > > > > > new eytzinger0_find_test_val() wrapper that calls it.
> > > > > > >
> > > > > > > We have already established that the array is sorted in eytzinger order,
> > > > > > > so we can use the eytzinger iterator functions and check the boundary
> > > > > > > conditions to verify the result of eytzinger0_find_le().
> > > > > > >
> > > > > > > Only scan the entire array if we get an incorrect result. When we need
> > > > > > > to scan, use eytzinger0_for_each_prev() so that we'll stop at the
> > > > > > > highest matching element in the array in case there are duplicates;
> > > > > > > going through the array linearly wouldn't give us that.
> > > > > >
> > > > > > For test code, wouldn't it be simpler to iterate over the test array,
> > > > > > testing with every element as a search value? There's enough corner
> > > > > > cases in lookup that I think it'd be worthwhile (and probably add some
> > > > > > extra test values, e.g. first/last elements +1/-1).
> > > > >
> > > > > If you expect to get the same index back, that won't work when there
> > > > > are duplicates.
> > > >
> > > > No, but we wouldn't expect to get the same index back if we're testing
> > > > every combination of elements (+0, -1, +1) x (le, ge, gt) - and it
> > > > sounds like perhaps we should, if you've been finding bugs. Thoughts?
> > >
> > > I don't really know what you're after here. Function
> > > eytzinger0_find_test() already tests every combination of elements
> > > (+0, -1, +1) x (le, ge, gt).
> >
> > Ok - it can be hard to tell looking at isolated patches vs. being able
> > to fetch a git repo. Do you have it in a branch I can fetch from?
> >
> > > The full scans of the array in eytzinger0_find_test_{le,gt,ge}() are
> > > not there to verify correctness; they're only there to produce
> > > slightly nicer debug output. I'm perfectly happy with removing that if
> > > you prefer.
> >
> > No, not at all
> >
> > > > I think the test code would have to do short linear searches from the
> > > > test element, and then verify the search functions against that.
> > >
> > > What for? We already know from the eytzinger0_for_each loop in
> > > eytzinger0_find_test() that the array is in eytzinger sort order, and
> > > we also know from eytzinger{0,1}_test() that the _prev() and _next()
> > > functions are doing "the right thing". So the one thing left to verify
> > > in eytzinger0_find_test_{le,gt,ge}() is that all the search functions
> > > always return the boundary element. That's done by going to the next
> > > element in search order and by verifying that it no longer fulfils the
> > > search criterion.
> > >
> > > > Have you spotted any issues with searching over arrays with duplicate
> > > > elements?
> > >
> > > Only that eytzinger0_find_ge() didn't always find the first matching
> > > element in the array; see patches 17 and 18.
> >
> > Gotcha
> >
> > Ok, it sounds like everything I'm after is there - give me a git branch
> > so I can read through it that way and I'll be happy to merge when you
> > say it's ready
>
> Sure, I've pushed the patches here:
>
> https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcachefs
>
> Note that you don't want to merge the following patch:
>
> bcachefs: Run the eytzinger tests on modprobe
>
> And this minor one should probably be changed to use __maybe_unused or
> dropped; not sure which of the two options you prefer:
>
> bcachefs: remove dead code in is_aligned
That code is a cut and paste of sort.c, so we should just drop it - no
reason for those to diverge (and perhaps add a giant comment on where
it's from).
> I've only run the self tests. They seem to provide good coverage and I
> don't expect any trouble, but some real filesystem testing would be
> great.
I've fetched it to my repo and added it to the CI:
https://evilpiepirate.org/~testdashboard/ci?user=kmo&branch=eytzinger
