yaclib / yaclib Goto Github PK

Add benchmarks relative to the master.
It is proposed to measure push and execution of 4 types:
A task that is executed faster than

1. 1 us
2. 1 ms
3. 1 sec
4. 1 min

For deterministic we want deterministic time
https://en.cppreference.com/w/cpp/header/chrono

We only need the Clocks, and more specifically the now method.

https://github.com/google/sanitizers

Maybe add Valgrind, Hellgrind, or something else

Necessary for #6

Code coverage dont check header files, to avoid checking another libraries.

• Understand how to fix this for our internal headers

Check it https://github.com/marketplace/actions/include-what-you-use-github-action and add in CI

Check researches and implementations of shared future (e.g. libunifex, articles, etc.). Try to design and implement this abstraction.

• Add lazy::Run, which returns a special object (Sender concept): save functor on the stack and make method Get which return Future.
• Make method for Sender with same semantic as Future::Then.

Use all checks, otherwise, we will discuss which ones to disable in PR

Necessary for #6

This class execute only last N tasks using IExecutorPtr.

To implement use SPSC lock-free fixed-size queue (ring buffer)

• Mark code section in ITask
• Can be able to execute other ITask while waiting (dangerous) need more docs

• Check this https://github.com/boostorg/context
• Check this https://github.com/google/marl
• Check this https://gitlab.com/Lipovsky/context or this https://github.com/catboost/catboost/tree/master/util/system see context
• Write context for macOS x86_64
• Write context for Linux x86_64
• Write context for Windows x86_64
• Create issue for write context for other platforms
• Write stack allocation and trampoline for coroutine
• Write tests for switch context
• Write benchmark for switch context
• Write tests for stack allocation

Recommend to look at this link https://www.agner.org/optimize

This class should help to set service values for thread pool threads:

• Name
• Priority
• Callbacks before starting using thread IThreadPool, after ending using thread IThreadPool

It is also a cache of threads between the operating system and a set of user IThreadPool's with a dynamic size or lifetime that is different from the lifetime of the program.

Need to add benchmarks against at least some of these libraries:

• Make this another repo in the YACLib organization
• STL
• cppcoro
• libunifex
• oneTBB
• folly
• Boost.fiber
• ASIO
• taskflow
• thread-pool-cpp
• concurrencpp
• executors
• Qt
• marl
• OpenMP

ITask <=> Intrusive node + vtable + virtual void Call() = 0

detail::Task(functor<void()>) -> Functor member + public inheritance ITask, void Call() call functor<void()>

detail::CallbackTask(functor<void(Args...)>) -> Functor member + raw memory for Args + public inheritance ITask, void Call() call functor<void(Args...)>(Args...), method some like SetArgs(Args...)

CreateCallback <=> detail::CallbackTask(functor<void(Args...)>)
when we should execute callback and know its args we:
callback->SetArgs(args...);
tp->Execute(callback)
or if inline callback call
callback->Call(args....)

This class Execute() tasks strictly sequentially using IExecutorPtr.
To implement use Wait-free MPSC queue

• Take all tests from https://gitlab.com/Lipovsky/concurrency-course/-/blob/master/tasks/condvar/thread-pool/tests/unit/thread_pool.cpp
• Find some other open source thread pools implementations and check their tests
• Implement your tests if it necessary
• If you use sleeps in thread pool tests - make them smaller for CI (better do it through config.hpp and cmake)

• Use GitHub actions
• Build library, tests, benchmarks for all checked configurations
  • Linux + Clang
  • Linux + GCC
  • Windows + MSVC
  • OS X + AppleClang
  • Windows + other compilers (if possible)
  • Android + GCC (if possible)
  • Android + Clang (if possible)
  • IOS + AppleClang (if possible)
• Check with clang-format
• Check with clang-tidy #8
• Run tests with sanitizers #7

First of feel free to ask me(@MBkkt) any questions about this task, often the task may not be described in enough detail for devs who don't have the full context.

Make T SharedFuture<T>::Get() const;
"Allocate" the mutex inside the SharedFuture class, not on the stack as is the case with T Future::Get() &&

WhenAll combinator
Container<Future> -> Future<Container>
Container<Future> -> Future
Container maybe any std container or Args...

Generate automatically and upload to a project static site using GitHub and GitHub actons

See

• yaclib::Strand implementation
• https://github.com/facebookexperimental/libunifex/blob/main/include/unifex/async_mutex.hpp
• https://github.com/lewissbaker/cppcoro/blob/master/include/cppcoro/async_mutex.hpp
• https://github.com/facebook/folly/blob/main/folly/experimental/coro/Mutex.h

MAKE IT BETTER

• #108
• #107
• Fix typo, grammar, etc
• Fix undocumentated API
• Translate design doc to English and separate design/done/plan

https://docs.google.com/document/d/1yIAYmbvL3JxOKOjuCyon7JhW4cSv1wy5hC0ApeGMV9s/pub
Design doc

Also, see this golang/go#8899

I also think. if we will implement this, we should write to Dmitry, he wants us to mention him in the file or not. Also a license issue.

https://github.com/codacy/codacy-clang-tidy#usage

Make LastInlineCall
Make typed tests

https://en.cppreference.com/w/cpp/thread

yaclib::std::

C++ 17:

• thread
• get_id
• yield
• sleep_for
• sleep_until
• mutex
• timed_mutex
• recursive_mutex
• shared_mutex
• shared_timed_mutex
• once_flag
• call_once
• condition_variable
• condition_variable_any

C++ 20:

• jthread
• counting_semaphore
• binary_semaphore
• latch
• barrier
• atomic::wait/notify_one/all

Maybe?

• notify_all_at_thread_exit
• jthread::stop_token
• Thread cancellation

Definitely no.

• promise
• packaged_task
• future
• shared_future
• async

• Remove CallerCore
• Test ITask::Cancel
• Add WaitGroup: wait many futures without their invalidation and without overhead expect one mutex/condvar

struct WaitGroup { // not copy/move
  template<typename T>
  void Add(Future<T>& f) &;

  void Wait() &;
};

This abstraction will have to be used in intrusive containers.
Therefore, it needs to be allocated on the heap and there should be pointers to prev/next in it.

And don't forget to write tests

Main idea to create:

• Future<void> WhenAll(...); ... can be any type of futures
• Future<vector<T>> TakeAll(...); ... can be same type of futures
• Future<std::tuple<T...>> TakeAllArgs(...); ... can be any type of futures
• Future<void> WhenAny(...); ... can be any type of futures
• Future<vector<T>> TakeAny(...); ... can be same type of futures
• Future<std::tuple<T...>> TakeAnyArgs(...); ... can be any type of futures

IMailBoxTask это ITask с несколькими особенностями

• Владение ею шарится между пользователем и IExector (Если это не так то не используйте ее)
• В параметре конструктора она принимает число N, это число сколько раз она исполнится:
  Приведу паттерн использования:

auto task = CreateMailBoxTask(2, lamdda)
// when timer tick
any_executor->Execute(task);

Хочется, чтобы таска исполнялась минимальное число раз между количеством тиков и N.
Собственно N будет строгим минимумом тогда когда тики происходят быстрее чем таска исполняется,

TODO(MBkkt) Лучшее описание

• Implement IThreadPool
• Use fixed threads count
• Use IntusiveList and std::mutex
• Implement tests for IThreadPool

Write basic documentation using GitHub Flavored Markdown:

• /README.md - table of contents = links to other documentation entries.
• /docs/README.md - library overview.
• /docs/INSTALL.md - prerequisites and install options.
• /docs/DEPENDENCIES.md - library build dependencies.
• /docs/CODESTYLE.md - additional code style information (i. e. entries which couldn't be put in .clang-format).

Add implementation based on atomic finite state machine
Add tests

• Use CMake
• Make library static
• Create project structure like:
  • /                                        // root
  • /include/yaclib                  // public header files
  • /include/yaclib/executor   // executors
  • /include/yaclib/future       // future/promise
  • /src                                  // all source and private header files
  • /src/executor                   // executors
  • /src/future                       // future/promise
  • /test                                // tests
  • /bench                            // benchmarks
  • /doc                                // library overview and design docs
  • /example                        // example of library usage

But return Awaiter that works with co_await

1. Implement thread pool specialization for single thread using Wait-free MPSC queue
2. Make tests run for all specializations of the thread pool

std::random_device should be deterministic in deterministic tests

If we mix headers and links in markdown it incorrect render in doxygen. (For example, check SANITIZERS.md). Check how to fix this doxygen bug

See https://jothepro.github.io/doxygen-awesome-css/ for details

1. Don't forget to add @MBkkt to all PR
2. If the issue has no assignees or only @MBkkt is listed. You can ask for it yourself.
3. If @MBkkt is indicated in the issue as the assignee, you need to additionally discuss the implementation with him.

Check WhenAll examples and add WhenAny examples in documentation

WhenAny combinator
Container<Future> -> Future
Container maybe any std container or Args...

Implement more tests for future/promise

• Implement good TestAndSet spinlock

Write different implementations IThreadPool

• IntusiveList with std::mutex
• IntusiveList with spinlock
• IntusiveList with std::mutex per thread
• IntusiveList with spinlock per thread
• Michael Scott queue
• Michael Scott queue per thread
• Lock-free MPSC queue with std::mutex for consumers
• Lock-free MPSC queue with spinlock for consumers
• Lock-free MPSC queue per thread
• Lock-free MPSC queue with std::mutex and per-thread SPSC queue for consumers
• Lock-free MPSC queue with spinlock and per-thread SPSC queue for consumers
• Lock-free deque
• Lock-free deque per thread

And whatever else you can invent

• Benchmark their

P.S. per thread means you should use work-stealing or work-distribution