Parallel Search and Indexing

[johnpatek]

Hi @johnpatek, I’ve started working on mio., documentation generation and publishing are set up here: mio-docs.

Updates

• tests cleaned up using doctest (I usually use GoogleTest, but wanted to keep this lightweight).
• cmake cleanups: modularized only in subdirs with source files, not header‑only dirs.
• added and applied a .clang-format (LLVM‑based; feel free to suggest changes).
• new tools folder for automation scripts (linters, testing, coverage).
  • Long‑term: i am considering Codecov or Coveralls integration.
• benchmarks planned as time allows.
• I’ll open some pull request as changes are ready.

would you be open to proposing a project logo? , that will be very helpful, since i am planning to modernize the old doxygen style/layout.

I’d like to evolve mio into a lightweight lazy_loader library for efficient large‑file processing without loading the entire file into memory. Planned features include:

• parallel search: use C++11 threads to assign memory‑mapped chunks to different threads for find/insert/delete operations.
• index‑based access: build an index during the first parse so repeated lookups jump directly to the right memory page.
  • This will be developed in a separate feature branch and tested for thread safety.

Originally posted by @wissem01chiha in #12

I would like to figure out a way to build these features on top of the existing mapping framework. We can break this down into multiple subtasks.

[johnpatek]

@wissem01chiha I would like your input on this issue, but my initial plan is to break this change into two separate issues we can work on.

[wissem01chiha]

Hi @johnpatek , yes of course, sorry for the late replay, i am planning to start experimenting, in few weeks,

• parallel search my idea is in order to look for a single byte/char or a pattern in a large file we map the file using mio api into memory pages and one thread process one page , thus we can distribute the workload across many threads and reduce execution time (many be also the search algorithm complexity) , this is a early prototyping idea and need to check feasibly with c++11 multithreading features ( there is for sure more feature rich frameworks for asynchronous/multithreading programming in c++, but i'd like to keep it lightweight ), i need to write some code and check thread safety of the idea/implementation
• index‑based access, this is inspired from popular software tools (i think java, matlab no? ), in order to accelerate the previous explained process across multiple operations so the first time we build a-like cache for the file that holds basic data ( no idea for the moment , but i will look for references), thus , when we perform the same operation (search for , insert , ..) for the second/third time it will be faster then the first one, ( it will use the cache build the first time by the library ), once the file closed the file cache will be deleted and everything cleared , i know this idea is not know and many programming languages or software implants this if you face one of them please ping me here)
  meanwhile i will put extra code in a contrib/ folder to separate the contributed features from the original source code, and try to test it as much as i can,
  thanks very much again

[spudwa]

Hi @johnpatek I've been using mio for a few years to map a 400 GB file that I use as a circular file to simulate a 15-20TB file. Obviously it constantly gets over written but I also read/write randomly, sequentially write 1.5GB chunks. I have looked with envy at the linux madvise() function, large/huge memory pages but I'm basically left with what Windows has had since the 32 era. 64 bit has improved the memory map size but the API has remained pretty basic. The performance of my application is totally at the mercy of the Windows memory manager which is a black box although we have recently got PrefetchVirtualMemory(). Good luck

[johnpatek]

Hi @johnpatek I've been using mio for a few years to map a 400 GB file that I use as a circular file to simulate a 15-20TB file. Obviously it constantly gets over written but I also read/write randomly, sequentially write 1.5GB chunks. I have looked with envy at the linux madvise() function, large/huge memory pages but I'm basically left with what Windows has had since the 32 era. 64 bit has improved the memory map size but the API has remained pretty basic. The performance of my application is totally at the mercy of the Windows memory manager which is a black box although we have recently got PrefetchVirtualMemory(). Good luck

Hello @spudwa, I appreciate you taking the time to bring this up. Very interesting use case by the way.

From a cursory glance at the PrefetchVirtualMemory API, it looks like it roughly maps to madvise(..., ..., MADV_WILLNEED), but more of an order than a suggestion. I also see the flags parameter is reserved as 0 currently, which I hope/assume means they will update this in the future to provide more control based on the intended use of the memory. It also gives a warning about low memory conditions, which leads me to believe it is more willing to follow bad advice than the Linux kernel.

Platform observations aside, I can add an advise/prefetch wrapper as part of the mapping handle if you think that would be useful. Keep in mind I would expose a couple of flags that would be useless on Windows(for now at least). It would more closely resemble madvise, but effectively ignore everything that isn't WILLNEED and DONTNEED on Windows.

Questions, concerns, and suggestions are more than welcome. This is not a feature I have strong preferences about at the moment, so if there is something that would further benefit your project, please let me know.