On Thu, Feb 27, 2025 at 02:59:57PM -0800, Michel Lespinasse wrote: >On Wed, Feb 26, 2025 at 01:19:13PM +0000, Wei Yang wrote: >> On Wed, Feb 26, 2025 at 04:33:39AM +0000, Matthew Wilcox wrote: >> >On Wed, Feb 26, 2025 at 02:22:33AM +0000, Wei Yang wrote: >> >> On Tue, Feb 25, 2025 at 12:35:29PM +0000, Matthew Wilcox wrote: >> >> >On Mon, Feb 24, 2025 at 08:22:34PM -0800, Andrew Morton wrote: >> >> >> The patch titled >> >> >> Subject: lib/interval_tree: skip the check before go to the right subtree >> >> >> has been added to the -mm mm-nonmm-unstable branch. Its filename is >> >> >> lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch >> >> > >> >> >I don't think this patch should be added. There's no claim of any >> >> >performance win. Wei has a long history of tweaky little patches that >> >> >may or may not be buggy. The interval tree has been around a long time >> >> >and doesn't have a test suite. This feels like unnecessary risk. >> >> >> >> Your concern is understandable. A change in fundamental data structure should >> >> be very careful. But I thought we don't take things personal. >> > >> >This isn't personal. It's noting your history. >> > >> >If you want to add a test suite for the interval tree to the kernel, >> >that would be a useful set of patches. And it would remove my concern >> >if we can demonstrate that we've exercised the code paths that you're >> >modifying and everything is fine. >> >> Sure, if my understanding is correct, the test suite is supposed to be put >> tools/testing/, right? > >(I accidentally sent this privately at first, resending publicly now) > >I haven't touched the code much since I originally wrote it, but I >think the logic of Wei's patch is sound. > Thanks. >Even then, I agree a more robust test suite would be nice. There is an >existing suite at lib/interval_tree_test.c, but it's more oriented >towards performance testing that correctness. It would be nice if it >checked the interval tree invariants (i.e. that each node's ITSUBTREE >is the max of its ITLAST and its children's ITSUBTREE) between >operations, like lib/rbtree_test.c check_augmented() does. > >I know many people don't like test suites that involve randomness, but >personally I think verifying that inserting 1000 random nodes works as >expected, and repeating that test 10000 times or so, should give >reasonable confidence in this code. > Let me have a try. >-- >Michel "walken" Lespinasse -- Wei Yang Help you, Help me
