memory ls/walk/find algorithms

[smorken]

I was wondering if anyone had considered using a tree-based structure rather than flat structure for the in-memory implementation. For my current experimentation, use case I'm ending up with A LOT of calls to ls via walk and find calls, and that calls startswith very many times when many paths are stored in the flat structuring.

For me the in-memory implementation as it stands is not useable for when you have a significant number of paths. I guess maybe the in-memory implementation is intended more for testing, and less for production?

Any value in pursing an update to the in-memory implementation? Any workarounds or better approaches? I have considered fuse but it's not a cross platform dependency.

[martindurant]

For me the in-memory implementation as it stands is not useable for when you have a significant number of paths. I guess maybe the in-memory implementation is intended more for testing, and less for production?

That is absolutely true, and you see it used as a fixture throughout the test code, alongside local files, ftp and http (striving to hit each class of storage).

Any value in pursing an update to the in-memory implementation?

I don't have plans, but happy to see better/alternative approaches.
See also: #1905

[smorken]

I ended up drafting an implementation using combined prefix trie and simple path caching.

Its here:

https://github.com/smorken/triememfs

I don't have a lot of time for the needed refinements at the moment, but it does pass all of the fsspec abstract test cases and from basic informal benchmarking so far it's dramatically faster for walk/ls/find routines.

Will be using this script for something though and may keep pushing refinements for a while.

[martindurant]

Thanks for posting. You can of course publish this and might want to include it in fsspec.registry.known_implementations if you want others to benefit too - when you're ready, of course.