diff options
author | Haibo Huang <hhb@google.com> | 2020-05-15 20:59:13 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2020-05-15 20:59:13 +0000 |
commit | 9c7929fce49b06956fdf0f9bb4b1402c76b23e55 (patch) | |
tree | e5e242d87b75c0165976161c49c5481e657b3ad2 | |
parent | 3bc3e7374a22b4e3bfc7a4610f9e900fd371e032 (diff) | |
parent | 94cf2fca747619cd3a944b81dd1a049a31616b94 (diff) | |
download | pthreadpool-9c7929fce49b06956fdf0f9bb4b1402c76b23e55.tar.gz |
Upgrade pthreadpool to 9b2c0caf7d9843f25709178b0cd7030892a1ff88 am: 50c19eb2c9 am: 94500f8156 am: 608343ca3e am: 690d528229 am: 94cf2fca74
Change-Id: Ia1e76b8377d382b935f82304d5f7fcc092917f32
-rw-r--r-- | .gitignore | 12 | ||||
-rw-r--r-- | Android.bp | 21 | ||||
-rw-r--r-- | BUILD.bazel | 307 | ||||
-rw-r--r-- | CMakeLists.txt | 80 | ||||
-rw-r--r-- | METADATA | 4 | ||||
-rw-r--r-- | README.md | 2 | ||||
-rw-r--r-- | WORKSPACE | 38 | ||||
-rwxr-xr-x | configure.py | 10 | ||||
-rw-r--r-- | src/gcd.c | 136 | ||||
-rw-r--r-- | src/legacy-api.c (renamed from src/threadpool-legacy.c) | 15 | ||||
-rw-r--r-- | src/memory.c | 66 | ||||
-rw-r--r-- | src/portable-api.c | 1330 | ||||
-rw-r--r-- | src/pthreads.c | 463 | ||||
-rw-r--r-- | src/shim.c (renamed from src/threadpool-shim.c) | 18 | ||||
-rw-r--r-- | src/threadpool-atomics.h | 567 | ||||
-rw-r--r-- | src/threadpool-common.h | 75 | ||||
-rw-r--r-- | src/threadpool-object.h | 528 | ||||
-rw-r--r-- | src/threadpool-pthreads.c | 1702 | ||||
-rw-r--r-- | src/threadpool-utils.h | 49 | ||||
-rw-r--r-- | src/windows.c | 366 |
20 files changed, 3988 insertions, 1801 deletions
@@ -2,12 +2,18 @@ build.ninja # Build objects and artifacts -deps/ -build/ +bazel-bin +bazel-genfiles +bazel-out +bazel-testlogs +bazel-pthreadpool bin/ -obj/ +build/ +build-*/ +deps/ lib/ libs/ +obj/ *.pyc *.pyo @@ -18,18 +18,28 @@ cc_library_static { vendor_available: true, sdk_version: "current", srcs: [ - "src/threadpool-pthreads.c", - "src/threadpool-legacy.c", + "src/memory.c", + "src/portable-api.c", + "src/pthreads.c", ], cflags: [ - "-std=gnu11", "-O2", "-Wno-deprecated-declarations", "-Wno-missing-field-initializers", + "-DPTHREADPOOL_USE_CPUINFO=1", + "-DPTHREADPOOL_USE_CONDVAR=1", ], + c_std: "gnu11", header_libs: [ "fxdiv_headers", ], + shared_libs: [ + "liblog", + ], + static_libs: [ + "libcpuinfo", + "libclog", + ], } cc_test { @@ -43,7 +53,12 @@ cc_test { "-Wno-missing-field-initializers", ], stl: "libc++_static", + shared_libs: [ + "liblog", + ], static_libs: [ + "libclog", + "libcpuinfo", "libgmock_ndk", "libpthreadpool", ], diff --git a/BUILD.bazel b/BUILD.bazel new file mode 100644 index 0000000..af1401b --- /dev/null +++ b/BUILD.bazel @@ -0,0 +1,307 @@ +load("@rules_cc//cc:defs.bzl", "cc_binary", "cc_library", "cc_test") + +licenses(["notice"]) + +############################## pthreadpool library ############################# + +INTERNAL_HDRS = [ + "src/threadpool-atomics.h", + "src/threadpool-common.h", + "src/threadpool-object.h", + "src/threadpool-utils.h", +] + +PORTABLE_SRCS = [ + "src/memory.c", + "src/portable-api.c", +] + +PTHREADS_IMPL_SRCS = PORTABLE_SRCS + ["src/pthreads.c"] + +GCD_IMPL_SRCS = PORTABLE_SRCS + ["src/gcd.c"] + +SHIM_IMPL_SRCS = ["src/shim.c"] + +INTERNAL_HDRS = [ + "src/threadpool-atomics.h", + "src/threadpool-common.h", + "src/threadpool-object.h", + "src/threadpool-utils.h", +] + +PORTABLE_SRCS = [ + "src/memory.c", + "src/portable-api.c", +] + +PTHREADS_IMPL_SRCS = PORTABLE_SRCS + ["src/pthreads.c"] + +GCD_IMPL_SRCS = PORTABLE_SRCS + ["src/gcd.c"] + +WINDOWS_IMPL_SRCS = PORTABLE_SRCS + ["src/windows.c"] + +SHIM_IMPL_SRCS = ["src/shim.c"] + +cc_library( + name = "pthreadpool", + srcs = select({ + ":pthreadpool_sync_primitive_explicit_condvar": INTERNAL_HDRS + PTHREADS_IMPL_SRCS, + ":pthreadpool_sync_primitive_explicit_futex": INTERNAL_HDRS + PTHREADS_IMPL_SRCS, + ":pthreadpool_sync_primitive_explicit_gcd": INTERNAL_HDRS + GCD_IMPL_SRCS, + ":pthreadpool_sync_primitive_explicit_event": INTERNAL_HDRS + WINDOWS_IMPL_SRCS, + ":emscripten_with_threads": INTERNAL_HDRS + PTHREADS_IMPL_SRCS, + ":emscripten": SHIM_IMPL_SRCS, + ":macos_x86": INTERNAL_HDRS + GCD_IMPL_SRCS, + ":macos_x86_64": INTERNAL_HDRS + GCD_IMPL_SRCS, + ":ios": INTERNAL_HDRS + GCD_IMPL_SRCS, + ":windows_x86_64": INTERNAL_HDRS + WINDOWS_IMPL_SRCS, + ":windows_x86_64_msvc": INTERNAL_HDRS + WINDOWS_IMPL_SRCS, + "//conditions:default": INTERNAL_HDRS + PTHREADS_IMPL_SRCS, + }), + copts = [ + "-std=gnu11", + ] + select({ + ":optimized_build": ["-O2"], + "//conditions:default": [], + }) + select({ + ":linux_arm": ["-DPTHREADPOOL_USE_CPUINFO=1"], + ":linux_armhf": ["-DPTHREADPOOL_USE_CPUINFO=1"], + ":linux_aarch64": ["-DPTHREADPOOL_USE_CPUINFO=1"], + ":android_armv7": ["-DPTHREADPOOL_USE_CPUINFO=1"], + ":android_arm64": ["-DPTHREADPOOL_USE_CPUINFO=1"], + "//conditions:default": ["-DPTHREADPOOL_USE_CPUINFO=0"], + }) + select({ + ":pthreadpool_sync_primitive_explicit_condvar": [ + "-DPTHREADPOOL_USE_CONDVAR=1", + "-DPTHREADPOOL_USE_FUTEX=0", + "-DPTHREADPOOL_USE_GCD=0", + "-DPTHREADPOOL_USE_EVENT=0", + ], + ":pthreadpool_sync_primitive_explicit_futex": [ + "-DPTHREADPOOL_USE_CONDVAR=0", + "-DPTHREADPOOL_USE_FUTEX=1", + "-DPTHREADPOOL_USE_GCD=0", + "-DPTHREADPOOL_USE_EVENT=0", + ], + ":pthreadpool_sync_primitive_explicit_gcd": [ + "-DPTHREADPOOL_USE_CONDVAR=0", + "-DPTHREADPOOL_USE_FUTEX=0", + "-DPTHREADPOOL_USE_GCD=1", + "-DPTHREADPOOL_USE_EVENT=0", + ], + ":pthreadpool_sync_primitive_explicit_event": [ + "-DPTHREADPOOL_USE_CONDVAR=0", + "-DPTHREADPOOL_USE_FUTEX=0", + "-DPTHREADPOOL_USE_GCD=0", + "-DPTHREADPOOL_USE_EVENT=1", + ], + "//conditions:default": [], + }), + hdrs = [ + "include/pthreadpool.h", + ], + defines = [ + "PTHREADPOOL_NO_DEPRECATED_API", + ], + includes = [ + "include", + ], + linkopts = select({ + ":emscripten_with_threads": [ + "-s ALLOW_BLOCKING_ON_MAIN_THREAD=1", + "-s PTHREAD_POOL_SIZE=8", + ], + "//conditions:default": [], + }), + strip_include_prefix = "include", + deps = [ + "@FXdiv", + ] + select({ + ":linux_arm": ["@cpuinfo"], + ":linux_armhf": ["@cpuinfo"], + ":linux_aarch64": ["@cpuinfo"], + ":android_armv7": ["@cpuinfo"], + ":android_arm64": ["@cpuinfo"], + "//conditions:default": [], + }), + visibility = ["//visibility:public"], +) + +################################## Unit tests ################################## + +EMSCRIPTEN_TEST_LINKOPTS = [ + "-s ASSERTIONS=2", + "-s ERROR_ON_UNDEFINED_SYMBOLS=1", + "-s DEMANGLE_SUPPORT=1", + "-s EXIT_RUNTIME=1", + "-s ALLOW_MEMORY_GROWTH=0", + "-s TOTAL_MEMORY=67108864", # 64M +] + +cc_test( + name = "pthreadpool_test", + srcs = ["test/pthreadpool.cc"], + linkopts = select({ + ":emscripten": EMSCRIPTEN_TEST_LINKOPTS, + "//conditions:default": [], + }), + deps = [ + ":pthreadpool", + "@com_google_googletest//:gtest_main", + ], +) + +################################## Benchmarks ################################## + +EMSCRIPTEN_BENCHMARK_LINKOPTS = [ + "-s ASSERTIONS=1", + "-s ERROR_ON_UNDEFINED_SYMBOLS=1", + "-s EXIT_RUNTIME=1", + "-s ALLOW_MEMORY_GROWTH=0", +] + +cc_binary( + name = "latency_bench", + srcs = ["bench/latency.cc"], + linkopts = select({ + ":emscripten": EMSCRIPTEN_BENCHMARK_LINKOPTS, + "//conditions:default": [], + }), + deps = [ + ":pthreadpool", + "@com_google_benchmark//:benchmark", + ], +) + +cc_binary( + name = "throughput_bench", + srcs = ["bench/throughput.cc"], + linkopts = select({ + ":emscripten": EMSCRIPTEN_BENCHMARK_LINKOPTS, + "//conditions:default": [], + }), + deps = [ + ":pthreadpool", + "@com_google_benchmark//:benchmark", + ], +) + +############################# Build configurations ############################# + +# Synchronize workers using pthreads condition variable. +config_setting( + name = "pthreadpool_sync_primitive_explicit_condvar", + define_values = {"pthreadpool_sync_primitive": "condvar"}, +) + +# Synchronize workers using futex. +config_setting( + name = "pthreadpool_sync_primitive_explicit_futex", + define_values = {"pthreadpool_sync_primitive": "futex"}, +) + +# Synchronize workers using Grand Central Dispatch. +config_setting( + name = "pthreadpool_sync_primitive_explicit_gcd", + define_values = {"pthreadpool_sync_primitive": "gcd"}, +) + +# Synchronize workers using WinAPI event. +config_setting( + name = "pthreadpool_sync_primitive_explicit_event", + define_values = {"pthreadpool_sync_primitive": "event"}, +) + +config_setting( + name = "optimized_build", + values = { + "compilation_mode": "opt", + }, +) + +config_setting( + name = "linux_arm", + values = {"cpu": "arm"}, +) + +config_setting( + name = "linux_armhf", + values = {"cpu": "armhf"}, +) + +config_setting( + name = "linux_aarch64", + values = {"cpu": "aarch64"}, +) + +config_setting( + name = "android_armv7", + values = { + "crosstool_top": "//external:android/crosstool", + "cpu": "armeabi-v7a", + }, +) + +config_setting( + name = "android_arm64", + values = { + "crosstool_top": "//external:android/crosstool", + "cpu": "arm64-v8a", + }, +) + +# Note: we need to individually match x86 and x86-64 macOS rather than use +# catch-all "apple_platform_type": "macos" because that option defaults to +# "macos" even when building on Linux! +config_setting( + name = "macos_x86", + values = { + "apple_platform_type": "macos", + "cpu": "darwin", + }, +) + +config_setting( + name = "macos_x86_64", + values = { + "apple_platform_type": "macos", + "cpu": "darwin_x86_64", + }, +) + +config_setting( + name = "ios", + values = { + "crosstool_top": "@bazel_tools//tools/cpp:toolchain", + "apple_platform_type": "ios", + }, +) + +config_setting( + name = "windows_x86_64", + values = { + "cpu": "x64_windows", + }, +) + +config_setting( + name = "windows_x86_64_msvc", + values = { + "cpu": "x64_windows_msvc", + }, +) + +config_setting( + name = "emscripten", + values = { + "crosstool_top": "//toolchain:emscripten", + } +) + +config_setting( + name = "emscripten_with_threads", + values = { + "crosstool_top": "//toolchain:emscripten", + "copt": "-pthread", + } +) diff --git a/CMakeLists.txt b/CMakeLists.txt index 79a17a1..51b0105 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -1,7 +1,5 @@ CMAKE_MINIMUM_REQUIRED(VERSION 3.5 FATAL_ERROR) -INCLUDE(GNUInstallDirs) - # ---[ Project PROJECT(pthreadpool C CXX) @@ -9,6 +7,8 @@ PROJECT(pthreadpool C CXX) SET(PTHREADPOOL_LIBRARY_TYPE "default" CACHE STRING "Type of library (shared, static, or default) to build") SET_PROPERTY(CACHE PTHREADPOOL_LIBRARY_TYPE PROPERTY STRINGS default static shared) OPTION(PTHREADPOOL_ALLOW_DEPRECATED_API "Enable deprecated API functions" ON) +SET(PTHREADPOOL_SYNC_PRIMITIVE "default" CACHE STRING "Synchronization primitive (condvar, futex, gcd, event, or default) for worker threads") +SET_PROPERTY(CACHE PTHREADPOOL_SYNC_PRIMITIVE PROPERTY STRINGS default condvar futex gcd event) IF("${CMAKE_SOURCE_DIR}" STREQUAL "${PROJECT_SOURCE_DIR}") OPTION(PTHREADPOOL_BUILD_TESTS "Build pthreadpool unit tests" ON) OPTION(PTHREADPOOL_BUILD_BENCHMARKS "Build pthreadpool micro-benchmarks" ON) @@ -18,6 +18,8 @@ ELSE() ENDIF() # ---[ CMake options +INCLUDE(GNUInstallDirs) + IF(PTHREADPOOL_BUILD_TESTS) ENABLE_TESTING() ENDIF() @@ -39,21 +41,6 @@ IF(NOT DEFINED FXDIV_SOURCE_DIR) SET(FXDIV_SOURCE_DIR "${CMAKE_BINARY_DIR}/FXdiv-source" CACHE STRING "FXdiv source directory") ENDIF() -IF(CMAKE_SYSTEM_NAME MATCHES "^(Linux|Android)$" AND CMAKE_SYSTEM_PROCESSOR MATCHES "^(armv[5-8].*|aarch64)$") - IF(NOT DEFINED CPUINFO_SOURCE_DIR) - MESSAGE(STATUS "Downloading cpuinfo to ${CMAKE_BINARY_DIR}/cpuinfo-source (define CPUINFO_SOURCE_DIR to avoid it)") - CONFIGURE_FILE(cmake/DownloadCpuinfo.cmake "${CMAKE_BINARY_DIR}/cpuinfo-download/CMakeLists.txt") - EXECUTE_PROCESS(COMMAND "${CMAKE_COMMAND}" -G "${CMAKE_GENERATOR}" . - WORKING_DIRECTORY "${CMAKE_BINARY_DIR}/cpuinfo-download") - EXECUTE_PROCESS(COMMAND "${CMAKE_COMMAND}" --build . - WORKING_DIRECTORY "${CMAKE_BINARY_DIR}/cpuinfo-download") - SET(CPUINFO_SOURCE_DIR "${CMAKE_BINARY_DIR}/cpuinfo-source" CACHE STRING "cpuinfo source directory") - ENDIF() - SET(PTHREADPOOL_USE_CPUINFO ON) -ELSE() - SET(PTHREADPOOL_USE_CPUINFO OFF) -ENDIF() - IF(PTHREADPOOL_BUILD_TESTS AND NOT DEFINED GOOGLETEST_SOURCE_DIR) MESSAGE(STATUS "Downloading Google Test to ${CMAKE_BINARY_DIR}/googletest-source (define GOOGLETEST_SOURCE_DIR to avoid it)") CONFIGURE_FILE(cmake/DownloadGoogleTest.cmake "${CMAKE_BINARY_DIR}/googletest-download/CMakeLists.txt") @@ -76,20 +63,22 @@ ENDIF() # ---[ pthreadpool library IF(PTHREADPOOL_ALLOW_DEPRECATED_API) - SET(PTHREADPOOL_SRCS src/threadpool-legacy.c) + SET(PTHREADPOOL_SRCS src/legacy-api.c) ENDIF() -IF(CMAKE_SYSTEM_NAME STREQUAL "Emscripten") - LIST(APPEND PTHREADPOOL_SRCS src/threadpool-shim.c) +IF(EMSCRIPTEN) + LIST(APPEND PTHREADPOOL_SRCS src/shim.c) ELSE() - LIST(APPEND PTHREADPOOL_SRCS src/threadpool-pthreads.c) + LIST(APPEND PTHREADPOOL_SRCS src/portable-api.c src/memory.c) + IF(APPLE AND (PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "default" OR PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "gcd")) + LIST(APPEND PTHREADPOOL_SRCS src/gcd.c) + ELSEIF(CMAKE_SYSTEM_NAME MATCHES "^(Windows|CYGWIN|MSYS)$" AND (PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "default" OR PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "event")) + LIST(APPEND PTHREADPOOL_SRCS src/windows.c) + ELSE() + LIST(APPEND PTHREADPOOL_SRCS src/pthreads.c) + ENDIF() ENDIF() -IF(${CMAKE_VERSION} VERSION_LESS "3.0") - ADD_LIBRARY(pthreadpool_interface STATIC include/pthreadpool.h) - SET_TARGET_PROPERTIES(pthreadpool_interface PROPERTIES LINKER_LANGUAGE C) -ELSE() - ADD_LIBRARY(pthreadpool_interface INTERFACE) -ENDIF() +ADD_LIBRARY(pthreadpool_interface INTERFACE) TARGET_INCLUDE_DIRECTORIES(pthreadpool_interface INTERFACE include) IF(NOT PTHREADPOOL_ALLOW_DEPRECATED_API) TARGET_COMPILE_DEFINITIONS(pthreadpool_interface INTERFACE PTHREADPOOL_NO_DEPRECATED_API=1) @@ -106,6 +95,26 @@ ELSE() MESSAGE(FATAL_ERROR "Unsupported library type ${PTHREADPOOL_LIBRARY_TYPE}") ENDIF() +IF(PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "condvar") + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_FUTEX=0) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_GCD=0) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_EVENT=0) +ELSEIF(PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "futex") + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_FUTEX=1) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_GCD=0) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_EVENT=0) +ELSEIF(PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "gcd") + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_FUTEX=0) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_GCD=1) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_EVENT=0) +ELSEIF(PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "event") + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_FUTEX=0) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_GCD=0) + TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_EVENT=1) +ELSEIF(NOT PTHREADPOOL_SYNC_PRIMITIVE STREQUAL "default") + MESSAGE(FATAL_ERROR "Unsupported synchronization primitive ${PTHREADPOOL_SYNC_PRIMITIVE}") +ENDIF() + SET_TARGET_PROPERTIES(pthreadpool PROPERTIES C_STANDARD 11 C_EXTENSIONS NO) @@ -137,23 +146,6 @@ IF(NOT TARGET fxdiv) ENDIF() TARGET_LINK_LIBRARIES(pthreadpool PRIVATE fxdiv) -# ---[ Configure cpuinfo -IF(PTHREADPOOL_USE_CPUINFO) - IF(NOT TARGET cpuinfo) - SET(CPUINFO_BUILD_TOOLS OFF CACHE BOOL "") - SET(CPUINFO_BUILD_UNIT_TESTS OFF CACHE BOOL "") - SET(CPUINFO_BUILD_MOCK_TESTS OFF CACHE BOOL "") - SET(CPUINFO_BUILD_BENCHMARKS OFF CACHE BOOL "") - ADD_SUBDIRECTORY( - "${CPUINFO_SOURCE_DIR}" - "${CMAKE_BINARY_DIR}/cpuinfo") - ENDIF() - TARGET_LINK_LIBRARIES(pthreadpool PRIVATE cpuinfo) - TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_CPUINFO=1) -ELSE() - TARGET_COMPILE_DEFINITIONS(pthreadpool PRIVATE PTHREADPOOL_USE_CPUINFO=0) -ENDIF() - INSTALL(TARGETS pthreadpool LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR} ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR}) @@ -9,11 +9,11 @@ third_party { type: GIT value: "https://github.com/Maratyszcza/pthreadpool" } - version: "76042155a8b1e189c8f141429fd72219472c32e1" + version: "9b2c0caf7d9843f25709178b0cd7030892a1ff88" license_type: NOTICE last_upgrade_date { year: 2020 - month: 4 + month: 5 day: 1 } } @@ -13,7 +13,7 @@ It provides similar functionality to `#pragma omp parallel for`, but with additi * Run on user-specified or auto-detected number of threads. * Work-stealing scheduling for efficient work balancing. * Wait-free synchronization of work items. -* Compatible with Linux (including Android), macOS, iOS, MinGW, Emscripten environments. +* Compatible with Linux (including Android), macOS, iOS, Windows, Emscripten environments. * 100% unit tests coverage. * Throughput and latency microbenchmarks. diff --git a/WORKSPACE b/WORKSPACE new file mode 100644 index 0000000..4a44079 --- /dev/null +++ b/WORKSPACE @@ -0,0 +1,38 @@ +workspace(name = "pthreadpool") + +load("@bazel_tools//tools/build_defs/repo:http.bzl", "http_archive") + +# Bazel rule definitions +http_archive( + name = "rules_cc", + strip_prefix = "rules_cc-master", + urls = ["https://github.com/bazelbuild/rules_cc/archive/master.zip"], +) + +# Google Test framework, used by most unit-tests. +http_archive( + name = "com_google_googletest", + strip_prefix = "googletest-master", + urls = ["https://github.com/google/googletest/archive/master.zip"], +) + +# Google Benchmark library, used in micro-benchmarks. +http_archive( + name = "com_google_benchmark", + strip_prefix = "benchmark-master", + urls = ["https://github.com/google/benchmark/archive/master.zip"], +) + +# FXdiv library, used for repeated integer division by the same factor +http_archive( + name = "FXdiv", + strip_prefix = "FXdiv-f7dd0576a1c8289ef099d4fd8b136b1c4487a873", + sha256 = "6e4b6e3c58e67c3bb090e286c4f235902c89b98cf3e67442a18f9167963aa286", + urls = ["https://github.com/Maratyszcza/FXdiv/archive/f7dd0576a1c8289ef099d4fd8b136b1c4487a873.zip"], +) + +# Android NDK location and version is auto-detected from $ANDROID_NDK_HOME environment variable +android_ndk_repository(name = "androidndk") + +# Android SDK location and API is auto-detected from $ANDROID_HOME environment variable +android_sdk_repository(name = "androidsdk") diff --git a/configure.py b/configure.py index fd4ce92..51b9b62 100755 --- a/configure.py +++ b/configure.py @@ -12,11 +12,15 @@ def main(args): build.export_cpath("include", ["pthreadpool.h"]) with build.options(source_dir="src", extra_include_dirs="src", deps=build.deps.fxdiv): - sources = ["threadpool-legacy.c"] + sources = ["legacy-api.c", "portable-api.c"] if build.target.is_emscripten: - sources.append("threadpool-shim.c") + sources.append("shim.c") + elif build.target.is_macos: + sources.append("gcd.c") + elif build.target.is_windows: + sources.append("windows.c") else: - sources.append("threadpool-pthreads.c") + sources.append("pthreads.c") build.static_library("pthreadpool", [build.cc(src) for src in sources]) with build.options(source_dir="test", deps=[build, build.deps.googletest]): diff --git a/src/gcd.c b/src/gcd.c new file mode 100644 index 0000000..ddd9af4 --- /dev/null +++ b/src/gcd.c @@ -0,0 +1,136 @@ +/* Standard C headers */ +#include <assert.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +/* Configuration header */ +#include "threadpool-common.h" + +/* Mach headers */ +#include <dispatch/dispatch.h> +#include <sys/types.h> +#include <sys/sysctl.h> + +/* Public library header */ +#include <pthreadpool.h> + +/* Internal library headers */ +#include "threadpool-atomics.h" +#include "threadpool-object.h" +#include "threadpool-utils.h" + +static void thread_main(void* arg, size_t thread_index) { + struct pthreadpool* threadpool = (struct pthreadpool*) arg; + struct thread_info* thread = &threadpool->threads[thread_index]; + + const uint32_t flags = pthreadpool_load_relaxed_uint32_t(&threadpool->flags); + const thread_function_t thread_function = + (thread_function_t) pthreadpool_load_relaxed_void_p(&threadpool->thread_function); + + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + + thread_function(threadpool, thread); + + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } +} + +struct pthreadpool* pthreadpool_create(size_t threads_count) { + if (threads_count == 0) { + int threads = 1; + size_t sizeof_threads = sizeof(threads); + if (sysctlbyname("hw.logicalcpu_max", &threads, &sizeof_threads, NULL, 0) != 0) { + return NULL; + } + + if (threads <= 0) { + return NULL; + } + + threads_count = (size_t) threads; + } + + struct pthreadpool* threadpool = pthreadpool_allocate(threads_count); + if (threadpool == NULL) { + return NULL; + } + threadpool->threads_count = fxdiv_init_size_t(threads_count); + for (size_t tid = 0; tid < threads_count; tid++) { + threadpool->threads[tid].thread_number = tid; + } + + /* Thread pool with a single thread computes everything on the caller thread. */ + if (threads_count > 1) { + threadpool->execution_semaphore = dispatch_semaphore_create(1); + } + return threadpool; +} + +PTHREADPOOL_INTERNAL void pthreadpool_parallelize( + struct pthreadpool* threadpool, + thread_function_t thread_function, + const void* params, + size_t params_size, + void* task, + void* context, + size_t linear_range, + uint32_t flags) +{ + assert(threadpool != NULL); + assert(thread_function != NULL); + assert(task != NULL); + assert(linear_range > 1); + + /* Protect the global threadpool structures */ + dispatch_semaphore_wait(threadpool->execution_semaphore, DISPATCH_TIME_FOREVER); + + /* Setup global arguments */ + pthreadpool_store_relaxed_void_p(&threadpool->thread_function, (void*) thread_function); + pthreadpool_store_relaxed_void_p(&threadpool->task, task); + pthreadpool_store_relaxed_void_p(&threadpool->argument, context); + pthreadpool_store_relaxed_uint32_t(&threadpool->flags, flags); + + /* Locking of completion_mutex not needed: readers are sleeping on command_condvar */ + const struct fxdiv_divisor_size_t threads_count = threadpool->threads_count; + + if (params_size != 0) { + memcpy(&threadpool->params, params, params_size); + } + + /* Spread the work between threads */ + const struct fxdiv_result_size_t range_params = fxdiv_divide_size_t(linear_range, threads_count); + size_t range_start = 0; + for (size_t tid = 0; tid < threads_count.value; tid++) { + struct thread_info* thread = &threadpool->threads[tid]; + const size_t range_length = range_params.quotient + (size_t) (tid < range_params.remainder); + const size_t range_end = range_start + range_length; + pthreadpool_store_relaxed_size_t(&thread->range_start, range_start); + pthreadpool_store_relaxed_size_t(&thread->range_end, range_end); + pthreadpool_store_relaxed_size_t(&thread->range_length, range_length); + + /* The next subrange starts where the previous ended */ + range_start = range_end; + } + + dispatch_apply_f(threads_count.value, DISPATCH_APPLY_AUTO, threadpool, thread_main); + + /* Unprotect the global threadpool structures */ + dispatch_semaphore_signal(threadpool->execution_semaphore); +} + +void pthreadpool_destroy(struct pthreadpool* threadpool) { + if (threadpool != NULL) { + if (threadpool->execution_semaphore != NULL) { + /* Release resources */ + dispatch_release(threadpool->execution_semaphore); + } + pthreadpool_deallocate(threadpool); + } +} diff --git a/src/threadpool-legacy.c b/src/legacy-api.c index 43fb798..8d5a6fd 100644 --- a/src/threadpool-legacy.c +++ b/src/legacy-api.c @@ -4,21 +4,12 @@ /* Dependencies */ #include <fxdiv.h> -/* Library header */ +/* Public library header */ #include <pthreadpool.h> +/* Internal library headers */ +#include "threadpool-utils.h" -static inline size_t divide_round_up(size_t dividend, size_t divisor) { - if (dividend % divisor == 0) { - return dividend / divisor; - } else { - return dividend / divisor + 1; - } -} - -static inline size_t min(size_t a, size_t b) { - return a < b ? a : b; -} void pthreadpool_compute_1d( pthreadpool_t threadpool, diff --git a/src/memory.c b/src/memory.c new file mode 100644 index 0000000..fc0d83e --- /dev/null +++ b/src/memory.c @@ -0,0 +1,66 @@ +/* Standard C headers */ +#include <assert.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> + +/* POSIX headers */ +#ifdef __ANDROID__ + #include <malloc.h> +#endif + +/* Windows headers */ +#ifdef _WIN32 + #include <malloc.h> +#endif + +/* Internal library headers */ +#include "threadpool-common.h" +#include "threadpool-object.h" + + +PTHREADPOOL_INTERNAL struct pthreadpool* pthreadpool_allocate( + size_t threads_count) +{ + assert(threads_count >= 1); + + const size_t threadpool_size = sizeof(struct pthreadpool) + threads_count * sizeof(struct thread_info); + struct pthreadpool* threadpool = NULL; + #if defined(__ANDROID__) + /* + * Android didn't get posix_memalign until API level 17 (Android 4.2). + * Use (otherwise obsolete) memalign function on Android platform. + */ + threadpool = memalign(PTHREADPOOL_CACHELINE_SIZE, threadpool_size); + if (threadpool == NULL) { + return NULL; + } + #elif defined(_WIN32) + threadpool = _aligned_malloc(threadpool_size, PTHREADPOOL_CACHELINE_SIZE); + if (threadpool == NULL) { + return NULL; + } + #else + if (posix_memalign((void**) &threadpool, PTHREADPOOL_CACHELINE_SIZE, threadpool_size) != 0) { + return NULL; + } + #endif + memset(threadpool, 0, threadpool_size); + return threadpool; +} + + +PTHREADPOOL_INTERNAL void pthreadpool_deallocate( + struct pthreadpool* threadpool) +{ + assert(threadpool != NULL); + + const size_t threadpool_size = sizeof(struct pthreadpool) + threadpool->threads_count.value * sizeof(struct thread_info); + memset(threadpool, 0, threadpool_size); + + #ifdef _WIN32 + _aligned_free(threadpool); + #else + free(threadpool); + #endif +} diff --git a/src/portable-api.c b/src/portable-api.c new file mode 100644 index 0000000..84d6eda --- /dev/null +++ b/src/portable-api.c @@ -0,0 +1,1330 @@ +/* Standard C headers */ +#include <assert.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +#if PTHREADPOOL_USE_CPUINFO + #include <cpuinfo.h> +#endif + +/* Dependencies */ +#include <fxdiv.h> + +/* Public library header */ +#include <pthreadpool.h> + +/* Internal library headers */ +#include "threadpool-atomics.h" +#include "threadpool-object.h" +#include "threadpool-utils.h" + + +size_t pthreadpool_get_threads_count(struct pthreadpool* threadpool) { + if (threadpool == NULL) { + return 1; + } + + return threadpool->threads_count.value; +} + +static void thread_parallelize_1d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_1d_t task = (pthreadpool_task_1d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + /* Process thread's own range of items */ + size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, range_start++); + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + task(argument, index); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_1d_with_uarch(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_1d_with_id_t task = (pthreadpool_task_1d_with_id_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + const uint32_t default_uarch_index = threadpool->params.parallelize_1d_with_uarch.default_uarch_index; + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > threadpool->params.parallelize_1d_with_uarch.max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + /* Process thread's own range of items */ + size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, uarch_index, range_start++); + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + task(argument, uarch_index, index); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_1d_tile_1d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_1d_tile_1d_t task = (pthreadpool_task_1d_tile_1d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const size_t tile = threadpool->params.parallelize_1d_tile_1d.tile; + size_t tile_start = range_start * tile; + + const size_t range = threadpool->params.parallelize_1d_tile_1d.range; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, tile_start, min(range - tile_start, tile)); + tile_start += tile; + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t tile_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const size_t tile_start = tile_index * tile; + task(argument, tile_start, min(range - tile_start, tile)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_2d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_2d_t task = (pthreadpool_task_2d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_2d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(range_start, range_j); + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, j); + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(linear_index, range_j); + task(argument, index_i_j.quotient, index_i_j.remainder); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_2d_tile_1d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_2d_tile_1d_t task = (pthreadpool_task_2d_tile_1d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_j = threadpool->params.parallelize_2d_tile_1d.tile_range_j; + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(range_start, tile_range_j); + const size_t tile_j = threadpool->params.parallelize_2d_tile_1d.tile_j; + size_t i = tile_index_i_j.quotient; + size_t start_j = tile_index_i_j.remainder * tile_j; + + const size_t range_j = threadpool->params.parallelize_2d_tile_1d.range_j; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, start_j, min(range_j - start_j, tile_j)); + start_j += tile_j; + if (start_j >= range_j) { + start_j = 0; + i += 1; + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(linear_index, tile_range_j); + const size_t start_j = tile_index_i_j.remainder * tile_j; + task(argument, tile_index_i_j.quotient, start_j, min(range_j - start_j, tile_j)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_2d_tile_2d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_2d_tile_2d_t task = (pthreadpool_task_2d_tile_2d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_j = threadpool->params.parallelize_2d_tile_2d.tile_range_j; + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(range_start, tile_range_j); + const size_t tile_i = threadpool->params.parallelize_2d_tile_2d.tile_i; + const size_t tile_j = threadpool->params.parallelize_2d_tile_2d.tile_j; + size_t start_i = tile_index_i_j.quotient * tile_i; + size_t start_j = tile_index_i_j.remainder * tile_j; + + const size_t range_i = threadpool->params.parallelize_2d_tile_2d.range_i; + const size_t range_j = threadpool->params.parallelize_2d_tile_2d.range_j; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, start_i, start_j, min(range_i - start_i, tile_i), min(range_j - start_j, tile_j)); + start_j += tile_j; + if (start_j >= range_j) { + start_j = 0; + start_i += tile_i; + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(linear_index, tile_range_j); + const size_t start_i = tile_index_i_j.quotient * tile_i; + const size_t start_j = tile_index_i_j.remainder * tile_j; + task(argument, start_i, start_j, min(range_i - start_i, tile_i), min(range_j - start_j, tile_j)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_2d_tile_2d_with_uarch(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_2d_tile_2d_with_id_t task = (pthreadpool_task_2d_tile_2d_with_id_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + const uint32_t default_uarch_index = threadpool->params.parallelize_2d_tile_2d_with_uarch.default_uarch_index; + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > threadpool->params.parallelize_2d_tile_2d_with_uarch.max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + /* Process thread's own range of items */ + const struct fxdiv_divisor_size_t tile_range_j = threadpool->params.parallelize_2d_tile_2d_with_uarch.tile_range_j; + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_result_size_t index = fxdiv_divide_size_t(range_start, tile_range_j); + const size_t range_i = threadpool->params.parallelize_2d_tile_2d_with_uarch.range_i; + const size_t tile_i = threadpool->params.parallelize_2d_tile_2d_with_uarch.tile_i; + const size_t range_j = threadpool->params.parallelize_2d_tile_2d_with_uarch.range_j; + const size_t tile_j = threadpool->params.parallelize_2d_tile_2d_with_uarch.tile_j; + size_t start_i = index.quotient * tile_i; + size_t start_j = index.remainder * tile_j; + + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, uarch_index, start_i, start_j, min(range_i - start_i, tile_i), min(range_j - start_j, tile_j)); + start_j += tile_j; + if (start_j >= range_j) { + start_j = 0; + start_i += tile_i; + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(linear_index, tile_range_j); + const size_t start_i = tile_index_i_j.quotient * tile_i; + const size_t start_j = tile_index_i_j.remainder * tile_j; + task(argument, uarch_index, start_i, start_j, min(range_i - start_i, tile_i), min(range_j - start_j, tile_j)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_3d_tile_2d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_3d_tile_2d_t task = (pthreadpool_task_3d_tile_2d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_k = threadpool->params.parallelize_3d_tile_2d.tile_range_k; + const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(range_start, tile_range_k); + const struct fxdiv_divisor_size_t tile_range_j = threadpool->params.parallelize_3d_tile_2d.tile_range_j; + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, tile_range_j); + const size_t tile_j = threadpool->params.parallelize_3d_tile_2d.tile_j; + const size_t tile_k = threadpool->params.parallelize_3d_tile_2d.tile_k; + size_t i = tile_index_i_j.quotient; + size_t start_j = tile_index_i_j.remainder * tile_j; + size_t start_k = tile_index_ij_k.remainder * tile_k; + + const size_t range_k = threadpool->params.parallelize_3d_tile_2d.range_k; + const size_t range_j = threadpool->params.parallelize_3d_tile_2d.range_j; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, start_j, start_k, min(range_j - start_j, tile_j), min(range_k - start_k, tile_k)); + start_k += tile_k; + if (start_k >= range_k) { + start_k = 0; + start_j += tile_j; + if (start_j >= range_j) { + start_j = 0; + i += 1; + } + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(linear_index, tile_range_k); + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, tile_range_j); + const size_t start_j = tile_index_i_j.remainder * tile_j; + const size_t start_k = tile_index_ij_k.remainder * tile_k; + task(argument, tile_index_i_j.quotient, start_j, start_k, min(range_j - start_j, tile_j), min(range_k - start_k, tile_k)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_3d_tile_2d_with_uarch(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_3d_tile_2d_with_id_t task = (pthreadpool_task_3d_tile_2d_with_id_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + const uint32_t default_uarch_index = threadpool->params.parallelize_3d_tile_2d_with_uarch.default_uarch_index; + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > threadpool->params.parallelize_3d_tile_2d_with_uarch.max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_k = threadpool->params.parallelize_3d_tile_2d_with_uarch.tile_range_k; + const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(range_start, tile_range_k); + const struct fxdiv_divisor_size_t tile_range_j = threadpool->params.parallelize_3d_tile_2d_with_uarch.tile_range_j; + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, tile_range_j); + const size_t tile_j = threadpool->params.parallelize_3d_tile_2d_with_uarch.tile_j; + const size_t tile_k = threadpool->params.parallelize_3d_tile_2d_with_uarch.tile_k; + size_t i = tile_index_i_j.quotient; + size_t start_j = tile_index_i_j.remainder * tile_j; + size_t start_k = tile_index_ij_k.remainder * tile_k; + + const size_t range_k = threadpool->params.parallelize_3d_tile_2d_with_uarch.range_k; + const size_t range_j = threadpool->params.parallelize_3d_tile_2d_with_uarch.range_j; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, uarch_index, i, start_j, start_k, min(range_j - start_j, tile_j), min(range_k - start_k, tile_k)); + start_k += tile_k; + if (start_k >= range_k) { + start_k = 0; + start_j += tile_j; + if (start_j >= range_j) { + start_j = 0; + i += 1; + } + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(linear_index, tile_range_k); + const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, tile_range_j); + const size_t start_j = tile_index_i_j.remainder * tile_j; + const size_t start_k = tile_index_ij_k.remainder * tile_k; + task(argument, uarch_index, tile_index_i_j.quotient, start_j, start_k, min(range_j - start_j, tile_j), min(range_k - start_k, tile_k)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_4d_tile_2d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_4d_tile_2d_t task = (pthreadpool_task_4d_tile_2d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_kl = threadpool->params.parallelize_4d_tile_2d.tile_range_kl; + const struct fxdiv_result_size_t tile_index_ij_kl = fxdiv_divide_size_t(range_start, tile_range_kl); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_4d_tile_2d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(tile_index_ij_kl.quotient, range_j); + const struct fxdiv_divisor_size_t tile_range_l = threadpool->params.parallelize_4d_tile_2d.tile_range_l; + const struct fxdiv_result_size_t tile_index_k_l = fxdiv_divide_size_t(tile_index_ij_kl.remainder, tile_range_l); + const size_t tile_k = threadpool->params.parallelize_4d_tile_2d.tile_k; + const size_t tile_l = threadpool->params.parallelize_4d_tile_2d.tile_l; + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t start_k = tile_index_k_l.quotient * tile_k; + size_t start_l = tile_index_k_l.remainder * tile_l; + + const size_t range_l = threadpool->params.parallelize_4d_tile_2d.range_l; + const size_t range_k = threadpool->params.parallelize_4d_tile_2d.range_k; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, j, start_k, start_l, min(range_k - start_k, tile_k), min(range_l - start_l, tile_l)); + start_l += tile_l; + if (start_l >= range_l) { + start_l = 0; + start_k += tile_k; + if (start_k >= range_k) { + start_k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ij_kl = fxdiv_divide_size_t(linear_index, tile_range_kl); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(tile_index_ij_kl.quotient, range_j); + const struct fxdiv_result_size_t tile_index_k_l = fxdiv_divide_size_t(tile_index_ij_kl.remainder, tile_range_l); + const size_t start_k = tile_index_k_l.quotient * tile_k; + const size_t start_l = tile_index_k_l.remainder * tile_l; + task(argument, index_i_j.quotient, index_i_j.remainder, start_k, start_l, min(range_k - start_k, tile_k), min(range_l - start_l, tile_l)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_4d_tile_2d_with_uarch(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_4d_tile_2d_with_id_t task = (pthreadpool_task_4d_tile_2d_with_id_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + const uint32_t default_uarch_index = threadpool->params.parallelize_4d_tile_2d_with_uarch.default_uarch_index; + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > threadpool->params.parallelize_4d_tile_2d_with_uarch.max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_kl = threadpool->params.parallelize_4d_tile_2d_with_uarch.tile_range_kl; + const struct fxdiv_result_size_t tile_index_ij_kl = fxdiv_divide_size_t(range_start, tile_range_kl); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_4d_tile_2d_with_uarch.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(tile_index_ij_kl.quotient, range_j); + const struct fxdiv_divisor_size_t tile_range_l = threadpool->params.parallelize_4d_tile_2d_with_uarch.tile_range_l; + const struct fxdiv_result_size_t tile_index_k_l = fxdiv_divide_size_t(tile_index_ij_kl.remainder, tile_range_l); + const size_t tile_k = threadpool->params.parallelize_4d_tile_2d_with_uarch.tile_k; + const size_t tile_l = threadpool->params.parallelize_4d_tile_2d_with_uarch.tile_l; + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t start_k = tile_index_k_l.quotient * tile_k; + size_t start_l = tile_index_k_l.remainder * tile_l; + + const size_t range_l = threadpool->params.parallelize_4d_tile_2d_with_uarch.range_l; + const size_t range_k = threadpool->params.parallelize_4d_tile_2d_with_uarch.range_k; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, uarch_index, i, j, start_k, start_l, min(range_k - start_k, tile_k), min(range_l - start_l, tile_l)); + start_l += tile_l; + if (start_l >= range_l) { + start_l = 0; + start_k += tile_k; + if (start_k >= range_k) { + start_k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ij_kl = fxdiv_divide_size_t(linear_index, tile_range_kl); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(tile_index_ij_kl.quotient, range_j); + const struct fxdiv_result_size_t tile_index_k_l = fxdiv_divide_size_t(tile_index_ij_kl.remainder, tile_range_l); + const size_t start_k = tile_index_k_l.quotient * tile_k; + const size_t start_l = tile_index_k_l.remainder * tile_l; + task(argument, uarch_index, index_i_j.quotient, index_i_j.remainder, start_k, start_l, min(range_k - start_k, tile_k), min(range_l - start_l, tile_l)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_5d_tile_2d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_5d_tile_2d_t task = (pthreadpool_task_5d_tile_2d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_lm = threadpool->params.parallelize_5d_tile_2d.tile_range_lm; + const struct fxdiv_result_size_t tile_index_ijk_lm = fxdiv_divide_size_t(range_start, tile_range_lm); + const struct fxdiv_divisor_size_t range_k = threadpool->params.parallelize_5d_tile_2d.range_k; + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lm.quotient, range_k); + const struct fxdiv_divisor_size_t tile_range_m = threadpool->params.parallelize_5d_tile_2d.tile_range_m; + const struct fxdiv_result_size_t tile_index_l_m = fxdiv_divide_size_t(tile_index_ijk_lm.remainder, tile_range_m); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_5d_tile_2d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const size_t tile_l = threadpool->params.parallelize_5d_tile_2d.tile_l; + const size_t tile_m = threadpool->params.parallelize_5d_tile_2d.tile_m; + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t k = index_ij_k.remainder; + size_t start_l = tile_index_l_m.quotient * tile_l; + size_t start_m = tile_index_l_m.remainder * tile_m; + + const size_t range_m = threadpool->params.parallelize_5d_tile_2d.range_m; + const size_t range_l = threadpool->params.parallelize_5d_tile_2d.range_l; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, j, k, start_l, start_m, min(range_l - start_l, tile_l), min(range_m - start_m, tile_m)); + start_m += tile_m; + if (start_m >= range_m) { + start_m = 0; + start_l += tile_l; + if (start_l >= range_l) { + start_l = 0; + if (++k == range_k.value) { + k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ijk_lm = fxdiv_divide_size_t(linear_index, tile_range_lm); + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lm.quotient, range_k); + const struct fxdiv_result_size_t tile_index_l_m = fxdiv_divide_size_t(tile_index_ijk_lm.remainder, tile_range_m); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const size_t start_l = tile_index_l_m.quotient * tile_l; + const size_t start_m = tile_index_l_m.remainder * tile_m; + task(argument, index_i_j.quotient, index_i_j.remainder, index_ij_k.remainder, + start_l, start_m, min(range_l - start_l, tile_l), min(range_m - start_m, tile_m)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_6d_tile_2d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_6d_tile_2d_t task = (pthreadpool_task_6d_tile_2d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_mn = threadpool->params.parallelize_6d_tile_2d.tile_range_mn; + const struct fxdiv_result_size_t tile_index_ijkl_mn = fxdiv_divide_size_t(range_start, tile_range_mn); + const struct fxdiv_divisor_size_t range_kl = threadpool->params.parallelize_6d_tile_2d.range_kl; + const struct fxdiv_result_size_t index_ij_kl = fxdiv_divide_size_t(tile_index_ijkl_mn.quotient, range_kl); + const struct fxdiv_divisor_size_t tile_range_n = threadpool->params.parallelize_6d_tile_2d.tile_range_n; + const struct fxdiv_result_size_t tile_index_m_n = fxdiv_divide_size_t(tile_index_ijkl_mn.remainder, tile_range_n); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_6d_tile_2d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_kl.quotient, range_j); + const struct fxdiv_divisor_size_t range_l = threadpool->params.parallelize_6d_tile_2d.range_l; + const struct fxdiv_result_size_t index_k_l = fxdiv_divide_size_t(index_ij_kl.remainder, range_l); + const size_t tile_m = threadpool->params.parallelize_6d_tile_2d.tile_m; + const size_t tile_n = threadpool->params.parallelize_6d_tile_2d.tile_n; + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t k = index_k_l.quotient; + size_t l = index_k_l.remainder; + size_t start_m = tile_index_m_n.quotient * tile_m; + size_t start_n = tile_index_m_n.remainder * tile_n; + + const size_t range_n = threadpool->params.parallelize_6d_tile_2d.range_n; + const size_t range_m = threadpool->params.parallelize_6d_tile_2d.range_m; + const size_t range_k = threadpool->params.parallelize_6d_tile_2d.range_k; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, j, k, l, start_m, start_n, min(range_m - start_m, tile_m), min(range_n - start_n, tile_n)); + start_n += tile_n; + if (start_n >= range_n) { + start_n = 0; + start_m += tile_m; + if (start_m >= range_m) { + start_m = 0; + if (++l == range_l.value) { + l = 0; + if (++k == range_k) { + k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + } + } + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ijkl_mn = fxdiv_divide_size_t(linear_index, tile_range_mn); + const struct fxdiv_result_size_t index_ij_kl = fxdiv_divide_size_t(tile_index_ijkl_mn.quotient, range_kl); + const struct fxdiv_result_size_t tile_index_m_n = fxdiv_divide_size_t(tile_index_ijkl_mn.remainder, tile_range_n); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_kl.quotient, range_j); + const struct fxdiv_result_size_t index_k_l = fxdiv_divide_size_t(index_ij_kl.remainder, range_l); + const size_t start_m = tile_index_m_n.quotient * tile_m; + const size_t start_n = tile_index_m_n.remainder * tile_n; + task(argument, index_i_j.quotient, index_i_j.remainder, index_k_l.quotient, index_k_l.remainder, + start_m, start_n, min(range_m - start_m, tile_m), min(range_n - start_n, tile_n)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +void pthreadpool_parallelize_1d( + struct pthreadpool* threadpool, + pthreadpool_task_1d_t task, + void* argument, + size_t range, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || range <= 1) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range; i++) { + task(argument, i); + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + pthreadpool_parallelize( + threadpool, &thread_parallelize_1d, NULL, 0, + (void*) task, argument, range, flags); + } +} + +void pthreadpool_parallelize_1d_with_uarch( + pthreadpool_t threadpool, + pthreadpool_task_1d_with_id_t task, + void* argument, + uint32_t default_uarch_index, + uint32_t max_uarch_index, + size_t range, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || range <= 1) { + /* No thread pool used: execute task sequentially on the calling thread */ + + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range; i++) { + task(argument, uarch_index, i); + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const struct pthreadpool_1d_with_uarch_params params = { + .default_uarch_index = default_uarch_index, + .max_uarch_index = max_uarch_index, + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_1d_with_uarch, ¶ms, sizeof(params), + task, argument, range, flags); + } +} + +void pthreadpool_parallelize_1d_tile_1d( + pthreadpool_t threadpool, + pthreadpool_task_1d_tile_1d_t task, + void* argument, + size_t range, + size_t tile, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || range <= tile) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range; i += tile) { + task(argument, i, min(range - i, tile)); + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const struct pthreadpool_1d_tile_1d_params params = { + .range = range, + .tile = tile, + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_1d_tile_1d, ¶ms, sizeof(params), + task, argument, divide_round_up(range, tile), flags); + } +} + +void pthreadpool_parallelize_2d( + pthreadpool_t threadpool, + pthreadpool_task_2d_t task, + void* argument, + size_t range_i, + size_t range_j, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || (range_i | range_j) <= 1) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + task(argument, i, j); + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const struct pthreadpool_2d_params params = { + .range_j = fxdiv_init_size_t(range_j), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_2d, ¶ms, sizeof(params), + task, argument, range_i * range_j, flags); + } +} + +void pthreadpool_parallelize_2d_tile_1d( + pthreadpool_t threadpool, + pthreadpool_task_2d_tile_1d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t tile_j, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || (range_i <= 1 && range_j <= tile_j)) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j += tile_j) { + task(argument, i, j, min(range_j - j, tile_j)); + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_j = divide_round_up(range_j, tile_j); + const struct pthreadpool_2d_tile_1d_params params = { + .range_j = range_j, + .tile_j = tile_j, + .tile_range_j = fxdiv_init_size_t(tile_range_j), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_2d_tile_1d, ¶ms, sizeof(params), + task, argument, range_i * tile_range_j, flags); + } +} + +void pthreadpool_parallelize_2d_tile_2d( + pthreadpool_t threadpool, + pthreadpool_task_2d_tile_2d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t tile_i, + size_t tile_j, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || (range_i <= tile_i && range_j <= tile_j)) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i += tile_i) { + for (size_t j = 0; j < range_j; j += tile_j) { + task(argument, i, j, min(range_i - i, tile_i), min(range_j - j, tile_j)); + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_i = divide_round_up(range_i, tile_i); + const size_t tile_range_j = divide_round_up(range_j, tile_j); + const struct pthreadpool_2d_tile_2d_params params = { + .range_i = range_i, + .tile_i = tile_i, + .range_j = range_j, + .tile_j = tile_j, + .tile_range_j = fxdiv_init_size_t(tile_range_j), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_2d_tile_2d, ¶ms, sizeof(params), + task, argument, tile_range_i * tile_range_j, flags); + } +} + +void pthreadpool_parallelize_2d_tile_2d_with_uarch( + pthreadpool_t threadpool, + pthreadpool_task_2d_tile_2d_with_id_t task, + void* argument, + uint32_t default_uarch_index, + uint32_t max_uarch_index, + size_t range_i, + size_t range_j, + size_t tile_i, + size_t tile_j, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || (range_i <= tile_i && range_j <= tile_j)) { + /* No thread pool used: execute task sequentially on the calling thread */ + + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i += tile_i) { + for (size_t j = 0; j < range_j; j += tile_j) { + task(argument, uarch_index, i, j, min(range_i - i, tile_i), min(range_j - j, tile_j)); + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_i = divide_round_up(range_i, tile_i); + const size_t tile_range_j = divide_round_up(range_j, tile_j); + const struct pthreadpool_2d_tile_2d_with_uarch_params params = { + .default_uarch_index = default_uarch_index, + .max_uarch_index = max_uarch_index, + .range_i = range_i, + .tile_i = tile_i, + .range_j = range_j, + .tile_j = tile_j, + .tile_range_j = fxdiv_init_size_t(tile_range_j), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_2d_tile_2d_with_uarch, ¶ms, sizeof(params), + task, argument, tile_range_i * tile_range_j, flags); + } +} + +void pthreadpool_parallelize_3d_tile_2d( + pthreadpool_t threadpool, + pthreadpool_task_3d_tile_2d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t tile_j, + size_t tile_k, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || (range_i <= 1 && range_j <= tile_j && range_k <= tile_k)) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j += tile_j) { + for (size_t k = 0; k < range_k; k += tile_k) { + task(argument, i, j, k, min(range_j - j, tile_j), min(range_k - k, tile_k)); + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_j = divide_round_up(range_j, tile_j); + const size_t tile_range_k = divide_round_up(range_k, tile_k); + const struct pthreadpool_3d_tile_2d_params params = { + .range_j = range_j, + .tile_j = tile_j, + .range_k = range_k, + .tile_k = tile_k, + .tile_range_j = fxdiv_init_size_t(tile_range_j), + .tile_range_k = fxdiv_init_size_t(tile_range_k), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_3d_tile_2d, ¶ms, sizeof(params), + task, argument, range_i * tile_range_j * tile_range_k, flags); + } +} + +void pthreadpool_parallelize_3d_tile_2d_with_uarch( + pthreadpool_t threadpool, + pthreadpool_task_3d_tile_2d_with_id_t task, + void* argument, + uint32_t default_uarch_index, + uint32_t max_uarch_index, + size_t range_i, + size_t range_j, + size_t range_k, + size_t tile_j, + size_t tile_k, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || (range_i <= 1 && range_j <= tile_j && range_k <= tile_k)) { + /* No thread pool used: execute task sequentially on the calling thread */ + + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j += tile_j) { + for (size_t k = 0; k < range_k; k += tile_k) { + task(argument, uarch_index, i, j, k, min(range_j - j, tile_j), min(range_k - k, tile_k)); + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_j = divide_round_up(range_j, tile_j); + const size_t tile_range_k = divide_round_up(range_k, tile_k); + const struct pthreadpool_3d_tile_2d_with_uarch_params params = { + .default_uarch_index = default_uarch_index, + .max_uarch_index = max_uarch_index, + .range_j = range_j, + .tile_j = tile_j, + .range_k = range_k, + .tile_k = tile_k, + .tile_range_j = fxdiv_init_size_t(tile_range_j), + .tile_range_k = fxdiv_init_size_t(tile_range_k), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_3d_tile_2d_with_uarch, ¶ms, sizeof(params), + task, argument, range_i * tile_range_j * tile_range_k, flags); + } +} + +void pthreadpool_parallelize_4d_tile_2d( + pthreadpool_t threadpool, + pthreadpool_task_4d_tile_2d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t tile_k, + size_t tile_l, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || ((range_i | range_j) <= 1 && range_k <= tile_k && range_l <= tile_l)) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k += tile_k) { + for (size_t l = 0; l < range_l; l += tile_l) { + task(argument, i, j, k, l, + min(range_k - k, tile_k), min(range_l - l, tile_l)); + } + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_l = divide_round_up(range_l, tile_l); + const size_t tile_range_kl = divide_round_up(range_k, tile_k) * tile_range_l; + const struct pthreadpool_4d_tile_2d_params params = { + .range_k = range_k, + .tile_k = tile_k, + .range_l = range_l, + .tile_l = tile_l, + .range_j = fxdiv_init_size_t(range_j), + .tile_range_kl = fxdiv_init_size_t(tile_range_kl), + .tile_range_l = fxdiv_init_size_t(tile_range_l), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_4d_tile_2d, ¶ms, sizeof(params), + task, argument, range_i * range_j * tile_range_kl, flags); + } +} + +void pthreadpool_parallelize_4d_tile_2d_with_uarch( + pthreadpool_t threadpool, + pthreadpool_task_4d_tile_2d_with_id_t task, + void* argument, + uint32_t default_uarch_index, + uint32_t max_uarch_index, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t tile_k, + size_t tile_l, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || ((range_i | range_j) <= 1 && range_k <= tile_k && range_l <= tile_l)) { + /* No thread pool used: execute task sequentially on the calling thread */ + + uint32_t uarch_index = default_uarch_index; + #if PTHREADPOOL_USE_CPUINFO + uarch_index = cpuinfo_get_current_uarch_index(); + if (uarch_index > max_uarch_index) { + uarch_index = default_uarch_index; + } + #endif + + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k += tile_k) { + for (size_t l = 0; l < range_l; l += tile_l) { + task(argument, uarch_index, i, j, k, l, + min(range_k - k, tile_k), min(range_l - l, tile_l)); + } + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_l = divide_round_up(range_l, tile_l); + const size_t tile_range_kl = divide_round_up(range_k, tile_k) * tile_range_l; + const struct pthreadpool_4d_tile_2d_with_uarch_params params = { + .default_uarch_index = default_uarch_index, + .max_uarch_index = max_uarch_index, + .range_k = range_k, + .tile_k = tile_k, + .range_l = range_l, + .tile_l = tile_l, + .range_j = fxdiv_init_size_t(range_j), + .tile_range_kl = fxdiv_init_size_t(tile_range_kl), + .tile_range_l = fxdiv_init_size_t(tile_range_l), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_4d_tile_2d_with_uarch, ¶ms, sizeof(params), + task, argument, range_i * range_j * tile_range_kl, flags); + } +} + +void pthreadpool_parallelize_5d_tile_2d( + pthreadpool_t threadpool, + pthreadpool_task_5d_tile_2d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t tile_l, + size_t tile_m, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || ((range_i | range_j | range_k) <= 1 && range_l <= tile_l && range_m <= tile_m)) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k++) { + for (size_t l = 0; l < range_l; l += tile_l) { + for (size_t m = 0; m < range_m; m += tile_m) { + task(argument, i, j, k, l, m, + min(range_l - l, tile_l), min(range_m - m, tile_m)); + } + } + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_m = divide_round_up(range_m, tile_m); + const size_t tile_range_lm = divide_round_up(range_l, tile_l) * tile_range_m; + const struct pthreadpool_5d_tile_2d_params params = { + .range_l = range_l, + .tile_l = tile_l, + .range_m = range_m, + .tile_m = tile_m, + .range_j = fxdiv_init_size_t(range_j), + .range_k = fxdiv_init_size_t(range_k), + .tile_range_lm = fxdiv_init_size_t(tile_range_lm), + .tile_range_m = fxdiv_init_size_t(tile_range_m), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_5d_tile_2d, ¶ms, sizeof(params), + task, argument, range_i * range_j * range_k * tile_range_lm, flags); + } +} + +void pthreadpool_parallelize_6d_tile_2d( + pthreadpool_t threadpool, + pthreadpool_task_6d_tile_2d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t range_n, + size_t tile_m, + size_t tile_n, + uint32_t flags) +{ + if (threadpool == NULL || threadpool->threads_count.value <= 1 || ((range_i | range_j | range_k | range_l) <= 1 && range_m <= tile_m && range_n <= tile_n)) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k++) { + for (size_t l = 0; l < range_l; l++) { + for (size_t m = 0; m < range_m; m += tile_m) { + for (size_t n = 0; n < range_n; n += tile_n) { + task(argument, i, j, k, l, m, n, + min(range_m - m, tile_m), min(range_n - n, tile_n)); + } + } + } + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t range_kl = range_k * range_l; + const size_t tile_range_n = divide_round_up(range_n, tile_n); + const size_t tile_range_mn = divide_round_up(range_m, tile_m) * tile_range_n; + const struct pthreadpool_6d_tile_2d_params params = { + .range_k = range_k, + .range_m = range_m, + .tile_m = tile_m, + .range_n = range_n, + .tile_n = tile_n, + .range_j = fxdiv_init_size_t(range_j), + .range_kl = fxdiv_init_size_t(range_kl), + .range_l = fxdiv_init_size_t(range_l), + .tile_range_mn = fxdiv_init_size_t(tile_range_mn), + .tile_range_n = fxdiv_init_size_t(tile_range_n), + }; + pthreadpool_parallelize( + threadpool, &thread_parallelize_6d_tile_2d, ¶ms, sizeof(params), + task, argument, range_i * range_j * range_kl * tile_range_mn, flags); + } +} diff --git a/src/pthreads.c b/src/pthreads.c new file mode 100644 index 0000000..2d945a0 --- /dev/null +++ b/src/pthreads.c @@ -0,0 +1,463 @@ +/* Standard C headers */ +#include <assert.h> +#include <limits.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +/* Configuration header */ +#include "threadpool-common.h" + +/* POSIX headers */ +#include <pthread.h> +#include <unistd.h> + +/* Futex-specific headers */ +#if PTHREADPOOL_USE_FUTEX + #if defined(__linux__) + #include <sys/syscall.h> + #include <linux/futex.h> + + /* Old Android NDKs do not define SYS_futex and FUTEX_PRIVATE_FLAG */ + #ifndef SYS_futex + #define SYS_futex __NR_futex + #endif + #ifndef FUTEX_PRIVATE_FLAG + #define FUTEX_PRIVATE_FLAG 128 + #endif + #elif defined(__EMSCRIPTEN__) + /* math.h for INFINITY constant */ + #include <math.h> + + #include <emscripten/threading.h> + #else + #error "Platform-specific implementation of futex_wait and futex_wake_all required" + #endif +#endif + +/* Windows-specific headers */ +#ifdef _WIN32 + #include <sysinfoapi.h> +#endif + +/* Dependencies */ +#if PTHREADPOOL_USE_CPUINFO + #include <cpuinfo.h> +#endif + +/* Public library header */ +#include <pthreadpool.h> + +/* Internal library headers */ +#include "threadpool-atomics.h" +#include "threadpool-object.h" +#include "threadpool-utils.h" + + +#if PTHREADPOOL_USE_FUTEX + #if defined(__linux__) + static int futex_wait(pthreadpool_atomic_uint32_t* address, uint32_t value) { + return syscall(SYS_futex, address, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, value, NULL); + } + + static int futex_wake_all(pthreadpool_atomic_uint32_t* address) { + return syscall(SYS_futex, address, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT_MAX); + } + #elif defined(__EMSCRIPTEN__) + static int futex_wait(pthreadpool_atomic_uint32_t* address, uint32_t value) { + return emscripten_futex_wait((volatile void*) address, value, INFINITY); + } + + static int futex_wake_all(pthreadpool_atomic_uint32_t* address) { + return emscripten_futex_wake((volatile void*) address, INT_MAX); + } + #else + #error "Platform-specific implementation of futex_wait and futex_wake_all required" + #endif +#endif + +static void checkin_worker_thread(struct pthreadpool* threadpool) { + #if PTHREADPOOL_USE_FUTEX + if (pthreadpool_decrement_fetch_relaxed_size_t(&threadpool->active_threads) == 0) { + pthreadpool_store_release_uint32_t(&threadpool->has_active_threads, 0); + futex_wake_all(&threadpool->has_active_threads); + } + #else + pthread_mutex_lock(&threadpool->completion_mutex); + if (pthreadpool_decrement_fetch_release_size_t(&threadpool->active_threads) == 0) { + pthread_cond_signal(&threadpool->completion_condvar); + } + pthread_mutex_unlock(&threadpool->completion_mutex); + #endif +} + +static void wait_worker_threads(struct pthreadpool* threadpool) { + /* Initial check */ + #if PTHREADPOOL_USE_FUTEX + uint32_t has_active_threads = pthreadpool_load_acquire_uint32_t(&threadpool->has_active_threads); + if (has_active_threads == 0) { + return; + } + #else + size_t active_threads = pthreadpool_load_acquire_size_t(&threadpool->active_threads); + if (active_threads == 0) { + return; + } + #endif + + /* Spin-wait */ + for (uint32_t i = PTHREADPOOL_SPIN_WAIT_ITERATIONS; i != 0; i--) { + /* This fence serves as a sleep instruction */ + pthreadpool_fence_acquire(); + + #if PTHREADPOOL_USE_FUTEX + has_active_threads = pthreadpool_load_acquire_uint32_t(&threadpool->has_active_threads); + if (has_active_threads == 0) { + return; + } + #else + active_threads = pthreadpool_load_acquire_size_t(&threadpool->active_threads); + if (active_threads == 0) { + return; + } + #endif + } + + /* Fall-back to mutex/futex wait */ + #if PTHREADPOOL_USE_FUTEX + while ((has_active_threads = pthreadpool_load_acquire_uint32_t(&threadpool->has_active_threads)) != 0) { + futex_wait(&threadpool->has_active_threads, 1); + } + #else + pthread_mutex_lock(&threadpool->completion_mutex); + while (pthreadpool_load_acquire_size_t(&threadpool->active_threads) != 0) { + pthread_cond_wait(&threadpool->completion_condvar, &threadpool->completion_mutex); + }; + pthread_mutex_unlock(&threadpool->completion_mutex); + #endif +} + +static uint32_t wait_for_new_command( + struct pthreadpool* threadpool, + uint32_t last_command, + uint32_t last_flags) +{ + uint32_t command = pthreadpool_load_acquire_uint32_t(&threadpool->command); + if (command != last_command) { + return command; + } + + if ((last_flags & PTHREADPOOL_FLAG_YIELD_WORKERS) == 0) { + /* Spin-wait loop */ + for (uint32_t i = PTHREADPOOL_SPIN_WAIT_ITERATIONS; i != 0; i--) { + /* This fence serves as a sleep instruction */ + pthreadpool_fence_acquire(); + + command = pthreadpool_load_acquire_uint32_t(&threadpool->command); + if (command != last_command) { + return command; + } + } + } + + /* Spin-wait disabled or timed out, fall back to mutex/futex wait */ + #if PTHREADPOOL_USE_FUTEX + do { + futex_wait(&threadpool->command, last_command); + command = pthreadpool_load_acquire_uint32_t(&threadpool->command); + } while (command == last_command); + #else + /* Lock the command mutex */ + pthread_mutex_lock(&threadpool->command_mutex); + /* Read the command */ + while ((command = pthreadpool_load_acquire_uint32_t(&threadpool->command)) == last_command) { + /* Wait for new command */ + pthread_cond_wait(&threadpool->command_condvar, &threadpool->command_mutex); + } + /* Read a new command */ + pthread_mutex_unlock(&threadpool->command_mutex); + #endif + return command; +} + +static void* thread_main(void* arg) { + struct thread_info* thread = (struct thread_info*) arg; + struct pthreadpool* threadpool = thread->threadpool; + uint32_t last_command = threadpool_command_init; + struct fpu_state saved_fpu_state = { 0 }; + uint32_t flags = 0; + + /* Check in */ + checkin_worker_thread(threadpool); + + /* Monitor new commands and act accordingly */ + for (;;) { + uint32_t command = wait_for_new_command(threadpool, last_command, flags); + pthreadpool_fence_acquire(); + + flags = pthreadpool_load_relaxed_uint32_t(&threadpool->flags); + + /* Process command */ + switch (command & THREADPOOL_COMMAND_MASK) { + case threadpool_command_parallelize: + { + const thread_function_t thread_function = + (thread_function_t) pthreadpool_load_relaxed_void_p(&threadpool->thread_function); + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + + thread_function(threadpool, thread); + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + break; + } + case threadpool_command_shutdown: + /* Exit immediately: the master thread is waiting on pthread_join */ + return NULL; + case threadpool_command_init: + /* To inhibit compiler warning */ + break; + } + /* Notify the master thread that we finished processing */ + checkin_worker_thread(threadpool); + /* Update last command */ + last_command = command; + }; +} + +struct pthreadpool* pthreadpool_create(size_t threads_count) { + #if PTHREADPOOL_USE_CPUINFO + if (!cpuinfo_initialize()) { + return NULL; + } + #endif + + if (threads_count == 0) { + #if PTHREADPOOL_USE_CPUINFO + threads_count = cpuinfo_get_processors_count(); + #elif defined(_SC_NPROCESSORS_ONLN) + threads_count = (size_t) sysconf(_SC_NPROCESSORS_ONLN); + #if defined(__EMSCRIPTEN_PTHREADS__) + /* Limit the number of threads to 8 to match link-time PTHREAD_POOL_SIZE option */ + if (threads_count >= 8) { + threads_count = 8; + } + #endif + #elif defined(_WIN32) + SYSTEM_INFO system_info; + ZeroMemory(&system_info, sizeof(system_info)); + GetSystemInfo(&system_info); + threads_count = (size_t) system_info.dwNumberOfProcessors; + #else + #error "Platform-specific implementation of sysconf(_SC_NPROCESSORS_ONLN) required" + #endif + } + + struct pthreadpool* threadpool = pthreadpool_allocate(threads_count); + if (threadpool == NULL) { + return NULL; + } + threadpool->threads_count = fxdiv_init_size_t(threads_count); + for (size_t tid = 0; tid < threads_count; tid++) { + threadpool->threads[tid].thread_number = tid; + threadpool->threads[tid].threadpool = threadpool; + } + + /* Thread pool with a single thread computes everything on the caller thread. */ + if (threads_count > 1) { + pthread_mutex_init(&threadpool->execution_mutex, NULL); + #if !PTHREADPOOL_USE_FUTEX + pthread_mutex_init(&threadpool->completion_mutex, NULL); + pthread_cond_init(&threadpool->completion_condvar, NULL); + pthread_mutex_init(&threadpool->command_mutex, NULL); + pthread_cond_init(&threadpool->command_condvar, NULL); + #endif + + #if PTHREADPOOL_USE_FUTEX + pthreadpool_store_relaxed_uint32_t(&threadpool->has_active_threads, 1); + #endif + pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); + + /* Caller thread serves as worker #0. Thus, we create system threads starting with worker #1. */ + for (size_t tid = 1; tid < threads_count; tid++) { + pthread_create(&threadpool->threads[tid].thread_object, NULL, &thread_main, &threadpool->threads[tid]); + } + + /* Wait until all threads initialize */ + wait_worker_threads(threadpool); + } + return threadpool; +} + +PTHREADPOOL_INTERNAL void pthreadpool_parallelize( + struct pthreadpool* threadpool, + thread_function_t thread_function, + const void* params, + size_t params_size, + void* task, + void* context, + size_t linear_range, + uint32_t flags) +{ + assert(threadpool != NULL); + assert(thread_function != NULL); + assert(task != NULL); + assert(linear_range > 1); + + /* Protect the global threadpool structures */ + pthread_mutex_lock(&threadpool->execution_mutex); + + #if !PTHREADPOOL_USE_FUTEX + /* Lock the command variables to ensure that threads don't start processing before they observe complete command with all arguments */ + pthread_mutex_lock(&threadpool->command_mutex); + #endif + + /* Setup global arguments */ + pthreadpool_store_relaxed_void_p(&threadpool->thread_function, (void*) thread_function); + pthreadpool_store_relaxed_void_p(&threadpool->task, task); + pthreadpool_store_relaxed_void_p(&threadpool->argument, context); + pthreadpool_store_relaxed_uint32_t(&threadpool->flags, flags); + + /* Locking of completion_mutex not needed: readers are sleeping on command_condvar */ + const struct fxdiv_divisor_size_t threads_count = threadpool->threads_count; + pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count.value - 1 /* caller thread */); + #if PTHREADPOOL_USE_FUTEX + pthreadpool_store_relaxed_uint32_t(&threadpool->has_active_threads, 1); + #endif + + if (params_size != 0) { + memcpy(&threadpool->params, params, params_size); + pthreadpool_fence_release(); + } + + /* Spread the work between threads */ + const struct fxdiv_result_size_t range_params = fxdiv_divide_size_t(linear_range, threads_count); + size_t range_start = 0; + for (size_t tid = 0; tid < threads_count.value; tid++) { + struct thread_info* thread = &threadpool->threads[tid]; + const size_t range_length = range_params.quotient + (size_t) (tid < range_params.remainder); + const size_t range_end = range_start + range_length; + pthreadpool_store_relaxed_size_t(&thread->range_start, range_start); + pthreadpool_store_relaxed_size_t(&thread->range_end, range_end); + pthreadpool_store_relaxed_size_t(&thread->range_length, range_length); + + /* The next subrange starts where the previous ended */ + range_start = range_end; + } + + /* + * Update the threadpool command. + * Imporantly, do it after initializing command parameters (range, task, argument, flags) + * ~(threadpool->command | THREADPOOL_COMMAND_MASK) flips the bits not in command mask + * to ensure the unmasked command is different then the last command, because worker threads + * monitor for change in the unmasked command. + */ + const uint32_t old_command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); + const uint32_t new_command = ~(old_command | THREADPOOL_COMMAND_MASK) | threadpool_command_parallelize; + + /* + * Store the command with release semantics to guarantee that if a worker thread observes + * the new command value, it also observes the updated command parameters. + * + * Note: release semantics is necessary even with a conditional variable, because the workers might + * be waiting in a spin-loop rather than the conditional variable. + */ + pthreadpool_store_release_uint32_t(&threadpool->command, new_command); + #if PTHREADPOOL_USE_FUTEX + /* Wake up the threads */ + futex_wake_all(&threadpool->command); + #else + /* Unlock the command variables before waking up the threads for better performance */ + pthread_mutex_unlock(&threadpool->command_mutex); + + /* Wake up the threads */ + pthread_cond_broadcast(&threadpool->command_condvar); + #endif + + /* Save and modify FPU denormals control, if needed */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + + /* Do computations as worker #0 */ + thread_function(threadpool, &threadpool->threads[0]); + + /* Restore FPU denormals control, if needed */ + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + + /* Wait until the threads finish computation */ + wait_worker_threads(threadpool); + + /* Make changes by other threads visible to this thread */ + pthreadpool_fence_acquire(); + + /* Unprotect the global threadpool structures */ + pthread_mutex_unlock(&threadpool->execution_mutex); +} + +void pthreadpool_destroy(struct pthreadpool* threadpool) { + if (threadpool != NULL) { + const size_t threads_count = threadpool->threads_count.value; + if (threads_count > 1) { + #if PTHREADPOOL_USE_FUTEX + pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); + pthreadpool_store_relaxed_uint32_t(&threadpool->has_active_threads, 1); + + /* + * Store the command with release semantics to guarantee that if a worker thread observes + * the new command value, it also observes the updated active_threads/has_active_threads values. + */ + pthreadpool_store_release_uint32_t(&threadpool->command, threadpool_command_shutdown); + + /* Wake up worker threads */ + futex_wake_all(&threadpool->command); + #else + /* Lock the command variable to ensure that threads don't shutdown until both command and active_threads are updated */ + pthread_mutex_lock(&threadpool->command_mutex); + + pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); + + /* + * Store the command with release semantics to guarantee that if a worker thread observes + * the new command value, it also observes the updated active_threads value. + * + * Note: the release fence inside pthread_mutex_unlock is insufficient, + * because the workers might be waiting in a spin-loop rather than the conditional variable. + */ + pthreadpool_store_release_uint32_t(&threadpool->command, threadpool_command_shutdown); + + /* Wake up worker threads */ + pthread_cond_broadcast(&threadpool->command_condvar); + + /* Commit the state changes and let workers start processing */ + pthread_mutex_unlock(&threadpool->command_mutex); + #endif + + /* Wait until all threads return */ + for (size_t thread = 1; thread < threads_count; thread++) { + pthread_join(threadpool->threads[thread].thread_object, NULL); + } + + /* Release resources */ + pthread_mutex_destroy(&threadpool->execution_mutex); + #if !PTHREADPOOL_USE_FUTEX + pthread_mutex_destroy(&threadpool->completion_mutex); + pthread_cond_destroy(&threadpool->completion_condvar); + pthread_mutex_destroy(&threadpool->command_mutex); + pthread_cond_destroy(&threadpool->command_condvar); + #endif + } + #if PTHREADPOOL_USE_CPUINFO + cpuinfo_deinitialize(); + #endif + pthreadpool_deallocate(threadpool); + } +} diff --git a/src/threadpool-shim.c b/src/shim.c index b5670ea..7bf378c 100644 --- a/src/threadpool-shim.c +++ b/src/shim.c @@ -1,14 +1,24 @@ /* Standard C headers */ #include <stddef.h> -/* Library header */ +/* Public library header */ #include <pthreadpool.h> -static inline size_t min(size_t a, size_t b) { - return a < b ? a : b; -} +/* Internal library headers */ +#include "threadpool-utils.h" + + +struct pthreadpool { +}; + +static const struct pthreadpool static_pthreadpool = { }; + struct pthreadpool* pthreadpool_create(size_t threads_count) { + if (threads_count <= 1) { + return (struct pthreadpool*) &static_pthreadpool; + } + return NULL; } diff --git a/src/threadpool-atomics.h b/src/threadpool-atomics.h index 92fcd8d..474d12b 100644 --- a/src/threadpool-atomics.h +++ b/src/threadpool-atomics.h @@ -4,6 +4,15 @@ #include <stddef.h> #include <stdint.h> +/* MSVC-specific headers */ +#ifdef _MSC_VER + #include <intrin.h> + #if defined(_M_IX86) || defined(_M_X64) || defined(_M_AMD64) + #include <immintrin.h> + #endif +#endif + + #if defined(__wasm__) && defined(__EMSCRIPTEN_PTHREADS__) && defined(__clang__) /* * Clang for WebAssembly target lacks stdatomic.h header, @@ -34,6 +43,18 @@ return __c11_atomic_load(address, __ATOMIC_RELAXED); } + static inline uint32_t pthreadpool_load_acquire_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return __c11_atomic_load(address, __ATOMIC_ACQUIRE); + } + + static inline size_t pthreadpool_load_acquire_size_t( + pthreadpool_atomic_size_t* address) + { + return __c11_atomic_load(address, __ATOMIC_ACQUIRE); + } + static inline void pthreadpool_store_relaxed_uint32_t( pthreadpool_atomic_uint32_t* address, uint32_t value) @@ -69,20 +90,30 @@ __c11_atomic_store(address, value, __ATOMIC_RELEASE); } - static inline uint32_t pthreadpool_fetch_sub_relaxed_size_t( - pthreadpool_atomic_size_t* address, - uint32_t decrement) + static inline size_t pthreadpool_decrement_fetch_relaxed_size_t( + pthreadpool_atomic_size_t* address) { - return __c11_atomic_fetch_sub(address, decrement, __ATOMIC_RELAXED); + return __c11_atomic_fetch_sub(address, 1, __ATOMIC_RELAXED) - 1; } - static inline bool pthreadpool_compare_exchange_weak_relaxed_size_t( - pthreadpool_atomic_size_t* address, - size_t* expected_value, - size_t new_value) + static inline size_t pthreadpool_decrement_fetch_release_size_t( + pthreadpool_atomic_size_t* address) { - return __c11_atomic_compare_exchange_weak( - address, expected_value, new_value, __ATOMIC_RELAXED, __ATOMIC_RELAXED); + return __c11_atomic_fetch_sub(address, 1, __ATOMIC_RELEASE) - 1; + } + + static inline bool pthreadpool_try_decrement_relaxed_size_t( + pthreadpool_atomic_size_t* value) + { + size_t actual_value = __c11_atomic_load(value, __ATOMIC_RELAXED); + while (actual_value != 0) { + if (__c11_atomic_compare_exchange_weak( + value, &actual_value, actual_value - 1, __ATOMIC_RELAXED, __ATOMIC_RELAXED)) + { + return true; + } + } + return false; } static inline void pthreadpool_fence_acquire() { @@ -92,7 +123,124 @@ static inline void pthreadpool_fence_release() { __c11_atomic_thread_fence(__ATOMIC_RELEASE); } -#else +#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_AMD64)) + typedef volatile uint32_t pthreadpool_atomic_uint32_t; + typedef volatile size_t pthreadpool_atomic_size_t; + typedef void *volatile pthreadpool_atomic_void_p; + + static inline uint32_t pthreadpool_load_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return *address; + } + + static inline size_t pthreadpool_load_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return *address; + } + + static inline void* pthreadpool_load_relaxed_void_p( + pthreadpool_atomic_void_p* address) + { + return *address; + } + + static inline uint32_t pthreadpool_load_acquire_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + /* x86-64 loads always have acquire semantics; use only a compiler barrier */ + const uint32_t value = *address; + _ReadBarrier(); + return value; + } + + static inline size_t pthreadpool_load_acquire_size_t( + pthreadpool_atomic_size_t* address) + { + /* x86-64 loads always have acquire semantics; use only a compiler barrier */ + const size_t value = *address; + _ReadBarrier(); + return value; + } + + static inline void pthreadpool_store_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + *address = value; + } + + static inline void pthreadpool_store_relaxed_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + *address = value; + } + + static inline void pthreadpool_store_relaxed_void_p( + pthreadpool_atomic_void_p* address, + void* value) + { + *address = value; + } + + static inline void pthreadpool_store_release_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + /* x86-64 stores always have release semantics; use only a compiler barrier */ + _WriteBarrier(); + *address = value; + } + + static inline void pthreadpool_store_release_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + /* x86-64 stores always have release semantics; use only a compiler barrier */ + _WriteBarrier(); + *address = value; + } + + static inline size_t pthreadpool_decrement_fetch_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement64((volatile __int64*) address); + } + + static inline size_t pthreadpool_decrement_fetch_release_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement64((volatile __int64*) address); + } + + static inline bool pthreadpool_try_decrement_relaxed_size_t( + pthreadpool_atomic_size_t* value) + { + size_t actual_value = *value; + while (actual_value != 0) { + const size_t new_value = actual_value - 1; + const size_t expected_value = actual_value; + actual_value = _InterlockedCompareExchange64( + (volatile __int64*) value, (__int64) new_value, (__int64) expected_value); + if (actual_value == expected_value) { + return true; + } + } + return false; + } + + static inline void pthreadpool_fence_acquire() { + _mm_lfence(); + _ReadBarrier(); + } + + static inline void pthreadpool_fence_release() { + _WriteBarrier(); + _mm_sfence(); + } +#elif defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L) #include <stdatomic.h> typedef _Atomic(uint32_t) pthreadpool_atomic_uint32_t; @@ -117,6 +265,18 @@ return atomic_load_explicit(address, memory_order_relaxed); } + static inline uint32_t pthreadpool_load_acquire_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return atomic_load_explicit(address, memory_order_acquire); + } + + static inline size_t pthreadpool_load_acquire_size_t( + pthreadpool_atomic_size_t* address) + { + return atomic_load_explicit(address, memory_order_acquire); + } + static inline void pthreadpool_store_relaxed_uint32_t( pthreadpool_atomic_uint32_t* address, uint32_t value) @@ -152,20 +312,42 @@ atomic_store_explicit(address, value, memory_order_release); } - static inline uint32_t pthreadpool_fetch_sub_relaxed_size_t( - pthreadpool_atomic_size_t* address, - uint32_t decrement) + static inline size_t pthreadpool_decrement_fetch_relaxed_size_t( + pthreadpool_atomic_size_t* address) { - return atomic_fetch_sub_explicit(address, decrement, memory_order_relaxed); + return atomic_fetch_sub_explicit(address, 1, memory_order_relaxed) - 1; } - static inline bool pthreadpool_compare_exchange_weak_relaxed_size_t( - pthreadpool_atomic_size_t* address, - size_t* expected_value, - size_t new_value) + static inline size_t pthreadpool_decrement_fetch_release_size_t( + pthreadpool_atomic_size_t* address) + { + return atomic_fetch_sub_explicit(address, 1, memory_order_release) - 1; + } + + static inline bool pthreadpool_try_decrement_relaxed_size_t( + pthreadpool_atomic_size_t* value) { - return atomic_compare_exchange_weak_explicit( - address, expected_value, new_value, memory_order_relaxed, memory_order_relaxed); + #if defined(__clang__) && (defined(__arm__) || defined(__aarch64__)) + size_t actual_value; + do { + actual_value = __builtin_arm_ldrex((const volatile size_t*) value); + if (actual_value == 0) { + __builtin_arm_clrex(); + return false; + } + } while (__builtin_arm_strex(actual_value - 1, (volatile size_t*) value) != 0); + return true; + #else + size_t actual_value = pthreadpool_load_relaxed_size_t(value); + while (actual_value != 0) { + if (atomic_compare_exchange_weak_explicit( + value, &actual_value, actual_value - 1, memory_order_relaxed, memory_order_relaxed)) + { + return true; + } + } + return false; + #endif } static inline void pthreadpool_fence_acquire() { @@ -175,4 +357,347 @@ static inline void pthreadpool_fence_release() { atomic_thread_fence(memory_order_release); } +#elif defined(_MSC_VER) && defined(_M_IX86) + typedef volatile uint32_t pthreadpool_atomic_uint32_t; + typedef volatile size_t pthreadpool_atomic_size_t; + typedef void *volatile pthreadpool_atomic_void_p; + + static inline uint32_t pthreadpool_load_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return *address; + } + + static inline size_t pthreadpool_load_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return *address; + } + + static inline void* pthreadpool_load_relaxed_void_p( + pthreadpool_atomic_void_p* address) + { + return *address; + } + + static inline uint32_t pthreadpool_load_acquire_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + /* x86 loads always have acquire semantics; use only a compiler barrier */ + const uint32_t value = *address; + _ReadBarrier(); + return value; + } + + static inline size_t pthreadpool_load_acquire_size_t( + pthreadpool_atomic_size_t* address) + { + /* x86 loads always have acquire semantics; use only a compiler barrier */ + const size_t value = *address; + _ReadBarrier(); + return value; + } + + static inline void pthreadpool_store_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + *address = value; + } + + static inline void pthreadpool_store_relaxed_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + *address = value; + } + + static inline void pthreadpool_store_relaxed_void_p( + pthreadpool_atomic_void_p* address, + void* value) + { + *address = value; + } + + static inline void pthreadpool_store_release_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + /* x86 stores always have release semantics; use only a compiler barrier */ + _WriteBarrier(); + *address = value; + } + + static inline void pthreadpool_store_release_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + /* x86 stores always have release semantics; use only a compiler barrier */ + _WriteBarrier(); + *address = value; + } + + static inline size_t pthreadpool_decrement_fetch_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement((volatile long*) address); + } + + static inline size_t pthreadpool_decrement_fetch_release_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement((volatile long*) address); + } + + static inline bool pthreadpool_try_decrement_relaxed_size_t( + pthreadpool_atomic_size_t* value) + { + size_t actual_value = *value; + while (actual_value != 0) { + const size_t new_value = actual_value - 1; + const size_t expected_value = actual_value; + actual_value = _InterlockedCompareExchange( + (volatile long*) value, (long) new_value, (long) expected_value); + if (actual_value == expected_value) { + return true; + } + } + return false; + } + + static inline void pthreadpool_fence_acquire() { + _mm_lfence(); + } + + static inline void pthreadpool_fence_release() { + _mm_sfence(); + } +#elif defined(_MSC_VER) && defined(_M_ARM64) + typedef volatile uint32_t pthreadpool_atomic_uint32_t; + typedef volatile size_t pthreadpool_atomic_size_t; + typedef void *volatile pthreadpool_atomic_void_p; + + static inline uint32_t pthreadpool_load_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return (uint32_t) __iso_volatile_load32((const volatile __int32*) address); + } + + static inline size_t pthreadpool_load_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) __iso_volatile_load64((const volatile __int64*) address); + } + + static inline void* pthreadpool_load_relaxed_void_p( + pthreadpool_atomic_void_p* address) + { + return (void*) __iso_volatile_load64((const volatile __int64*) address); + } + + static inline uint32_t pthreadpool_load_acquire_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return (uint32_t) __ldar32((volatile unsigned __int32*) address); + } + + static inline size_t pthreadpool_load_acquire_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) __ldar64((volatile unsigned __int64*) address); + } + + static inline void pthreadpool_store_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + __iso_volatile_store32((volatile __int32*) address, (__int32) value); + } + + static inline void pthreadpool_store_relaxed_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + __iso_volatile_store64((volatile __int64*) address, (__int64) value); + } + + static inline void pthreadpool_store_relaxed_void_p( + pthreadpool_atomic_void_p* address, + void* value) + { + __iso_volatile_store64((volatile __int64*) address, (__int64) value); + } + + static inline void pthreadpool_store_release_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + _WriteBarrier(); + __stlr32((unsigned __int32 volatile*) address, (unsigned __int32) value); + } + + static inline void pthreadpool_store_release_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + _WriteBarrier(); + __stlr64((unsigned __int64 volatile*) address, (unsigned __int64) value); + } + + static inline size_t pthreadpool_decrement_fetch_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement64_nf((volatile __int64*) address); + } + + static inline size_t pthreadpool_decrement_fetch_release_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement64_rel((volatile __int64*) address); + } + + static inline bool pthreadpool_try_decrement_relaxed_size_t( + pthreadpool_atomic_size_t* value) + { + size_t actual_value = (size_t) __iso_volatile_load64((const volatile __int64*) value); + while (actual_value != 0) { + const size_t new_value = actual_value - 1; + const size_t expected_value = actual_value; + actual_value = _InterlockedCompareExchange64_nf( + (volatile __int64*) value, (__int64) new_value, (__int64) expected_value); + if (actual_value == expected_value) { + return true; + } + } + return false; + } + + static inline void pthreadpool_fence_acquire() { + __dmb(_ARM64_BARRIER_ISHLD); + _ReadBarrier(); + } + + static inline void pthreadpool_fence_release() { + _WriteBarrier(); + __dmb(_ARM64_BARRIER_ISH); + } +#elif defined(_MSC_VER) && defined(_M_ARM) + typedef volatile uint32_t pthreadpool_atomic_uint32_t; + typedef volatile size_t pthreadpool_atomic_size_t; + typedef void *volatile pthreadpool_atomic_void_p; + + static inline uint32_t pthreadpool_load_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return (uint32_t) __iso_volatile_load32((const volatile __int32*) address); + } + + static inline size_t pthreadpool_load_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) __iso_volatile_load32((const volatile __int32*) address); + } + + static inline void* pthreadpool_load_relaxed_void_p( + pthreadpool_atomic_void_p* address) + { + return (void*) __iso_volatile_load32((const volatile __int32*) address); + } + + static inline uint32_t pthreadpool_load_acquire_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + const uint32_t value = (uint32_t) __iso_volatile_load32((const volatile __int32*) address); + __dmb(_ARM_BARRIER_ISH); + _ReadBarrier(); + return value; + } + + static inline size_t pthreadpool_load_acquire_size_t( + pthreadpool_atomic_size_t* address) + { + const size_t value = (size_t) __iso_volatile_load32((const volatile __int32*) address); + __dmb(_ARM_BARRIER_ISH); + _ReadBarrier(); + return value; + } + + static inline void pthreadpool_store_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + __iso_volatile_store32((volatile __int32*) address, (__int32) value); + } + + static inline void pthreadpool_store_relaxed_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + __iso_volatile_store32((volatile __int32*) address, (__int32) value); + } + + static inline void pthreadpool_store_relaxed_void_p( + pthreadpool_atomic_void_p* address, + void* value) + { + __iso_volatile_store32((volatile __int32*) address, (__int32) value); + } + + static inline void pthreadpool_store_release_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + _WriteBarrier(); + __dmb(_ARM_BARRIER_ISH); + __iso_volatile_store32((volatile __int32*) address, (__int32) value); + } + + static inline void pthreadpool_store_release_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + _WriteBarrier(); + __dmb(_ARM_BARRIER_ISH); + __iso_volatile_store32((volatile __int32*) address, (__int32) value); + } + + static inline size_t pthreadpool_decrement_fetch_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement_nf((volatile long*) address); + } + + static inline size_t pthreadpool_decrement_fetch_release_size_t( + pthreadpool_atomic_size_t* address) + { + return (size_t) _InterlockedDecrement_rel((volatile long*) address); + } + + static inline bool pthreadpool_try_decrement_relaxed_size_t( + pthreadpool_atomic_size_t* value) + { + size_t actual_value = (size_t) __iso_volatile_load32((const volatile __int32*) value); + while (actual_value != 0) { + const size_t new_value = actual_value - 1; + const size_t expected_value = actual_value; + actual_value = _InterlockedCompareExchange_nf( + (volatile long*) value, (long) new_value, (long) expected_value); + if (actual_value == expected_value) { + return true; + } + } + return false; + } + + static inline void pthreadpool_fence_acquire() { + __dmb(_ARM_BARRIER_ISH); + _ReadBarrier(); + } + + static inline void pthreadpool_fence_release() { + _WriteBarrier(); + __dmb(_ARM_BARRIER_ISH); + } +#else + #error "Platform-specific implementation of threadpool-atomics.h required" #endif diff --git a/src/threadpool-common.h b/src/threadpool-common.h new file mode 100644 index 0000000..ca84744 --- /dev/null +++ b/src/threadpool-common.h @@ -0,0 +1,75 @@ +#pragma once + +#ifndef PTHREADPOOL_USE_CPUINFO + #define PTHREADPOOL_USE_CPUINFO 0 +#endif + +#ifndef PTHREADPOOL_USE_FUTEX + #if defined(__linux__) + #define PTHREADPOOL_USE_FUTEX 1 + #elif defined(__EMSCRIPTEN__) + #define PTHREADPOOL_USE_FUTEX 1 + #else + #define PTHREADPOOL_USE_FUTEX 0 + #endif +#endif + +#ifndef PTHREADPOOL_USE_GCD + #if defined(__APPLE__) + #define PTHREADPOOL_USE_GCD 1 + #else + #define PTHREADPOOL_USE_GCD 0 + #endif +#endif + +#ifndef PTHREADPOOL_USE_EVENT + #if defined(_WIN32) || defined(__CYGWIN__) + #define PTHREADPOOL_USE_EVENT 1 + #else + #define PTHREADPOOL_USE_EVENT 0 + #endif +#endif + +#ifndef PTHREADPOOL_USE_CONDVAR + #if PTHREADPOOL_USE_GCD || PTHREADPOOL_USE_FUTEX || PTHREADPOOL_USE_EVENT + #define PTHREADPOOL_USE_CONDVAR 0 + #else + #define PTHREADPOOL_USE_CONDVAR 1 + #endif +#endif + + +/* Number of iterations in spin-wait loop before going into futex/condvar wait */ +#define PTHREADPOOL_SPIN_WAIT_ITERATIONS 1000000 + +#define PTHREADPOOL_CACHELINE_SIZE 64 +#if defined(__GNUC__) + #define PTHREADPOOL_CACHELINE_ALIGNED __attribute__((__aligned__(PTHREADPOOL_CACHELINE_SIZE))) +#elif defined(_MSC_VER) + #define PTHREADPOOL_CACHELINE_ALIGNED __declspec(align(PTHREADPOOL_CACHELINE_SIZE)) +#else + #error "Platform-specific implementation of PTHREADPOOL_CACHELINE_ALIGNED required" +#endif + +#if defined(__clang__) + #if __has_extension(c_static_assert) || __has_feature(c_static_assert) + #define PTHREADPOOL_STATIC_ASSERT(predicate, message) _Static_assert((predicate), message) + #else + #define PTHREADPOOL_STATIC_ASSERT(predicate, message) + #endif +#elif defined(__GNUC__) && ((__GNUC__ > 4) || (__GNUC__ == 4) && (__GNUC_MINOR__ >= 6)) + /* Static assert is supported by gcc >= 4.6 */ + #define PTHREADPOOL_STATIC_ASSERT(predicate, message) _Static_assert((predicate), message) +#else + #define PTHREADPOOL_STATIC_ASSERT(predicate, message) +#endif + +#ifndef PTHREADPOOL_INTERNAL + #if defined(__ELF__) + #define PTHREADPOOL_INTERNAL __attribute__((__visibility__("internal"))) + #elif defined(__MACH__) + #define PTHREADPOOL_INTERNAL __attribute__((__visibility__("hidden"))) + #else + #define PTHREADPOOL_INTERNAL + #endif +#endif diff --git a/src/threadpool-object.h b/src/threadpool-object.h new file mode 100644 index 0000000..239d116 --- /dev/null +++ b/src/threadpool-object.h @@ -0,0 +1,528 @@ +#pragma once + +/* Standard C headers */ +#include <stddef.h> +#include <stdint.h> + +/* Internal headers */ +#include "threadpool-common.h" +#include "threadpool-atomics.h" + +/* POSIX headers */ +#if PTHREADPOOL_USE_CONDVAR || PTHREADPOOL_USE_FUTEX +#include <pthread.h> +#endif + +/* Mach headers */ +#if PTHREADPOOL_USE_GCD +#include <dispatch/dispatch.h> +#endif + +/* Windows headers */ +#if PTHREADPOOL_USE_EVENT +#include <windows.h> +#endif + +/* Dependencies */ +#include <fxdiv.h> + +/* Library header */ +#include <pthreadpool.h> + + +#define THREADPOOL_COMMAND_MASK UINT32_C(0x7FFFFFFF) + +enum threadpool_command { + threadpool_command_init, + threadpool_command_parallelize, + threadpool_command_shutdown, +}; + +struct PTHREADPOOL_CACHELINE_ALIGNED thread_info { + /** + * Index of the first element in the work range. + * Before processing a new element the owning worker thread increments this value. + */ + pthreadpool_atomic_size_t range_start; + /** + * Index of the element after the last element of the work range. + * Before processing a new element the stealing worker thread decrements this value. + */ + pthreadpool_atomic_size_t range_end; + /** + * The number of elements in the work range. + * Due to race conditions range_length <= range_end - range_start. + * The owning worker thread must decrement this value before incrementing @a range_start. + * The stealing worker thread must decrement this value before decrementing @a range_end. + */ + pthreadpool_atomic_size_t range_length; + /** + * Thread number in the 0..threads_count-1 range. + */ + size_t thread_number; + /** + * Thread pool which owns the thread. + */ + struct pthreadpool* threadpool; +#if PTHREADPOOL_USE_CONDVAR || PTHREADPOOL_USE_FUTEX + /** + * The pthread object corresponding to the thread. + */ + pthread_t thread_object; +#endif +#if PTHREADPOOL_USE_EVENT + /** + * The Windows thread handle corresponding to the thread. + */ + HANDLE thread_handle; +#endif +}; + +PTHREADPOOL_STATIC_ASSERT(sizeof(struct thread_info) % PTHREADPOOL_CACHELINE_SIZE == 0, + "thread_info structure must occupy an integer number of cache lines (64 bytes)"); + +struct pthreadpool_1d_with_uarch_params { + /** + * Copy of the default_uarch_index argument passed to the pthreadpool_parallelize_1d_with_uarch function. + */ + uint32_t default_uarch_index; + /** + * Copy of the max_uarch_index argument passed to the pthreadpool_parallelize_1d_with_uarch function. + */ + uint32_t max_uarch_index; +}; + +struct pthreadpool_1d_tile_1d_params { + /** + * Copy of the range argument passed to the pthreadpool_parallelize_1d_tile_1d function. + */ + size_t range; + /** + * Copy of the tile argument passed to the pthreadpool_parallelize_1d_tile_1d function. + */ + size_t tile; +}; + +struct pthreadpool_2d_params { + /** + * FXdiv divisor for the range_j argument passed to the pthreadpool_parallelize_2d function. + */ + struct fxdiv_divisor_size_t range_j; +}; + +struct pthreadpool_2d_tile_1d_params { + /** + * Copy of the range_j argument passed to the pthreadpool_parallelize_2d_tile_1d function. + */ + size_t range_j; + /** + * Copy of the tile_j argument passed to the pthreadpool_parallelize_2d_tile_1d function. + */ + size_t tile_j; + /** + * FXdiv divisor for the divide_round_up(range_j, tile_j) value. + */ + struct fxdiv_divisor_size_t tile_range_j; +}; + +struct pthreadpool_2d_tile_2d_params { + /** + * Copy of the range_i argument passed to the pthreadpool_parallelize_2d_tile_2d function. + */ + size_t range_i; + /** + * Copy of the tile_i argument passed to the pthreadpool_parallelize_2d_tile_2d function. + */ + size_t tile_i; + /** + * Copy of the range_j argument passed to the pthreadpool_parallelize_2d_tile_2d function. + */ + size_t range_j; + /** + * Copy of the tile_j argument passed to the pthreadpool_parallelize_2d_tile_2d function. + */ + size_t tile_j; + /** + * FXdiv divisor for the divide_round_up(range_j, tile_j) value. + */ + struct fxdiv_divisor_size_t tile_range_j; +}; + +struct pthreadpool_2d_tile_2d_with_uarch_params { + /** + * Copy of the default_uarch_index argument passed to the pthreadpool_parallelize_2d_tile_2d_with_uarch function. + */ + uint32_t default_uarch_index; + /** + * Copy of the max_uarch_index argument passed to the pthreadpool_parallelize_2d_tile_2d_with_uarch function. + */ + uint32_t max_uarch_index; + /** + * Copy of the range_i argument passed to the pthreadpool_parallelize_2d_tile_2d_with_uarch function. + */ + size_t range_i; + /** + * Copy of the tile_i argument passed to the pthreadpool_parallelize_2d_tile_2d_with_uarch function. + */ + size_t tile_i; + /** + * Copy of the range_j argument passed to the pthreadpool_parallelize_2d_tile_2d_with_uarch function. + */ + size_t range_j; + /** + * Copy of the tile_j argument passed to the pthreadpool_parallelize_2d_tile_2d_with_uarch function. + */ + size_t tile_j; + /** + * FXdiv divisor for the divide_round_up(range_j, tile_j) value. + */ + struct fxdiv_divisor_size_t tile_range_j; +}; + +struct pthreadpool_3d_tile_2d_params { + /** + * Copy of the range_j argument passed to the pthreadpool_parallelize_3d_tile_2d function. + */ + size_t range_j; + /** + * Copy of the tile_j argument passed to the pthreadpool_parallelize_3d_tile_2d function. + */ + size_t tile_j; + /** + * Copy of the range_k argument passed to the pthreadpool_parallelize_3d_tile_2d function. + */ + size_t range_k; + /** + * Copy of the tile_k argument passed to the pthreadpool_parallelize_3d_tile_2d function. + */ + size_t tile_k; + /** + * FXdiv divisor for the divide_round_up(range_j, tile_j) value. + */ + struct fxdiv_divisor_size_t tile_range_j; + /** + * FXdiv divisor for the divide_round_up(range_k, tile_k) value. + */ + struct fxdiv_divisor_size_t tile_range_k; +}; + +struct pthreadpool_3d_tile_2d_with_uarch_params { + /** + * Copy of the default_uarch_index argument passed to the pthreadpool_parallelize_3d_tile_2d_with_uarch function. + */ + uint32_t default_uarch_index; + /** + * Copy of the max_uarch_index argument passed to the pthreadpool_parallelize_3d_tile_2d_with_uarch function. + */ + uint32_t max_uarch_index; + /** + * Copy of the range_j argument passed to the pthreadpool_parallelize_3d_tile_2d_with_uarch function. + */ + size_t range_j; + /** + * Copy of the tile_j argument passed to the pthreadpool_parallelize_3d_tile_2d_with_uarch function. + */ + size_t tile_j; + /** + * Copy of the range_k argument passed to the pthreadpool_parallelize_3d_tile_2d_with_uarch function. + */ + size_t range_k; + /** + * Copy of the tile_k argument passed to the pthreadpool_parallelize_3d_tile_2d_with_uarch function. + */ + size_t tile_k; + /** + * FXdiv divisor for the divide_round_up(range_j, tile_j) value. + */ + struct fxdiv_divisor_size_t tile_range_j; + /** + * FXdiv divisor for the divide_round_up(range_k, tile_k) value. + */ + struct fxdiv_divisor_size_t tile_range_k; +}; + +struct pthreadpool_4d_tile_2d_params { + /** + * Copy of the range_k argument passed to the pthreadpool_parallelize_4d_tile_2d function. + */ + size_t range_k; + /** + * Copy of the tile_k argument passed to the pthreadpool_parallelize_4d_tile_2d function. + */ + size_t tile_k; + /** + * Copy of the range_l argument passed to the pthreadpool_parallelize_4d_tile_2d function. + */ + size_t range_l; + /** + * Copy of the tile_l argument passed to the pthreadpool_parallelize_4d_tile_2d function. + */ + size_t tile_l; + /** + * FXdiv divisor for the range_j argument passed to the pthreadpool_parallelize_4d_tile_2d function. + */ + struct fxdiv_divisor_size_t range_j; + /** + * FXdiv divisor for the divide_round_up(range_k, tile_k) * divide_round_up(range_l, tile_l) value. + */ + struct fxdiv_divisor_size_t tile_range_kl; + /** + * FXdiv divisor for the divide_round_up(range_l, tile_l) value. + */ + struct fxdiv_divisor_size_t tile_range_l; +}; + +struct pthreadpool_4d_tile_2d_with_uarch_params { + /** + * Copy of the default_uarch_index argument passed to the pthreadpool_parallelize_4d_tile_2d_with_uarch function. + */ + uint32_t default_uarch_index; + /** + * Copy of the max_uarch_index argument passed to the pthreadpool_parallelize_4d_tile_2d_with_uarch function. + */ + uint32_t max_uarch_index; + /** + * Copy of the range_k argument passed to the pthreadpool_parallelize_4d_tile_2d_with_uarch function. + */ + size_t range_k; + /** + * Copy of the tile_k argument passed to the pthreadpool_parallelize_4d_tile_2d_with_uarch function. + */ + size_t tile_k; + /** + * Copy of the range_l argument passed to the pthreadpool_parallelize_4d_tile_2d_with_uarch function. + */ + size_t range_l; + /** + * Copy of the tile_l argument passed to the pthreadpool_parallelize_4d_tile_2d_with_uarch function. + */ + size_t tile_l; + /** + * FXdiv divisor for the range_j argument passed to the pthreadpool_parallelize_4d_tile_2d_with_uarch function. + */ + struct fxdiv_divisor_size_t range_j; + /** + * FXdiv divisor for the divide_round_up(range_k, tile_k) * divide_round_up(range_l, tile_l) value. + */ + struct fxdiv_divisor_size_t tile_range_kl; + /** + * FXdiv divisor for the divide_round_up(range_l, tile_l) value. + */ + struct fxdiv_divisor_size_t tile_range_l; +}; + +struct pthreadpool_5d_tile_2d_params { + /** + * Copy of the range_l argument passed to the pthreadpool_parallelize_5d_tile_2d function. + */ + size_t range_l; + /** + * Copy of the tile_l argument passed to the pthreadpool_parallelize_5d_tile_2d function. + */ + size_t tile_l; + /** + * Copy of the range_m argument passed to the pthreadpool_parallelize_5d_tile_2d function. + */ + size_t range_m; + /** + * Copy of the tile_m argument passed to the pthreadpool_parallelize_5d_tile_2d function. + */ + size_t tile_m; + /** + * FXdiv divisor for the range_j argument passed to the pthreadpool_parallelize_5d_tile_2d function. + */ + struct fxdiv_divisor_size_t range_j; + /** + * FXdiv divisor for the range_k argument passed to the pthreadpool_parallelize_5d_tile_2d function. + */ + struct fxdiv_divisor_size_t range_k; + /** + * FXdiv divisor for the divide_round_up(range_l, tile_l) * divide_round_up(range_m, tile_m) value. + */ + struct fxdiv_divisor_size_t tile_range_lm; + /** + * FXdiv divisor for the divide_round_up(range_m, tile_m) value. + */ + struct fxdiv_divisor_size_t tile_range_m; +}; + +struct pthreadpool_6d_tile_2d_params { + /** + * Copy of the range_k argument passed to the pthreadpool_parallelize_6d_tile_2d function. + */ + size_t range_k; + /** + * Copy of the range_m argument passed to the pthreadpool_parallelize_6d_tile_2d function. + */ + size_t range_m; + /** + * Copy of the tile_m argument passed to the pthreadpool_parallelize_6d_tile_2d function. + */ + size_t tile_m; + /** + * Copy of the range_n argument passed to the pthreadpool_parallelize_6d_tile_2d function. + */ + size_t range_n; + /** + * Copy of the tile_n argument passed to the pthreadpool_parallelize_6d_tile_2d function. + */ + size_t tile_n; + /** + * FXdiv divisor for the range_j argument passed to the pthreadpool_parallelize_6d_tile_2d function. + */ + struct fxdiv_divisor_size_t range_j; + /** + * FXdiv divisor for the range_k * range_l value. + */ + struct fxdiv_divisor_size_t range_kl; + /** + * FXdiv divisor for the range_l argument passed to the pthreadpool_parallelize_6d_tile_2d function. + */ + struct fxdiv_divisor_size_t range_l; + /** + * FXdiv divisor for the divide_round_up(range_m, tile_m) * divide_round_up(range_n, tile_n) value. + */ + struct fxdiv_divisor_size_t tile_range_mn; + /** + * FXdiv divisor for the divide_round_up(range_n, tile_n) value. + */ + struct fxdiv_divisor_size_t tile_range_n; +}; + +struct PTHREADPOOL_CACHELINE_ALIGNED pthreadpool { +#if !PTHREADPOOL_USE_GCD + /** + * The number of threads that are processing an operation. + */ + pthreadpool_atomic_size_t active_threads; +#endif +#if PTHREADPOOL_USE_FUTEX + /** + * Indicates if there are active threads. + * Only two values are possible: + * - has_active_threads == 0 if active_threads == 0 + * - has_active_threads == 1 if active_threads != 0 + */ + pthreadpool_atomic_uint32_t has_active_threads; +#endif +#if !PTHREADPOOL_USE_GCD + /** + * The last command submitted to the thread pool. + */ + pthreadpool_atomic_uint32_t command; +#endif + /** + * The entry point function to call for each thread in the thread pool for parallelization tasks. + */ + pthreadpool_atomic_void_p thread_function; + /** + * The function to call for each item. + */ + pthreadpool_atomic_void_p task; + /** + * The first argument to the item processing function. + */ + pthreadpool_atomic_void_p argument; + /** + * Additional parallelization parameters. + * These parameters are specific for each thread_function. + */ + union { + struct pthreadpool_1d_with_uarch_params parallelize_1d_with_uarch; + struct pthreadpool_1d_tile_1d_params parallelize_1d_tile_1d; + struct pthreadpool_2d_params parallelize_2d; + struct pthreadpool_2d_tile_1d_params parallelize_2d_tile_1d; + struct pthreadpool_2d_tile_2d_params parallelize_2d_tile_2d; + struct pthreadpool_2d_tile_2d_with_uarch_params parallelize_2d_tile_2d_with_uarch; + struct pthreadpool_3d_tile_2d_params parallelize_3d_tile_2d; + struct pthreadpool_3d_tile_2d_with_uarch_params parallelize_3d_tile_2d_with_uarch; + struct pthreadpool_4d_tile_2d_params parallelize_4d_tile_2d; + struct pthreadpool_4d_tile_2d_with_uarch_params parallelize_4d_tile_2d_with_uarch; + struct pthreadpool_5d_tile_2d_params parallelize_5d_tile_2d; + struct pthreadpool_6d_tile_2d_params parallelize_6d_tile_2d; + } params; + /** + * Copy of the flags passed to a parallelization function. + */ + pthreadpool_atomic_uint32_t flags; +#if PTHREADPOOL_USE_CONDVAR || PTHREADPOOL_USE_FUTEX + /** + * Serializes concurrent calls to @a pthreadpool_parallelize_* from different threads. + */ + pthread_mutex_t execution_mutex; +#endif +#if PTHREADPOOL_USE_GCD + /** + * Serializes concurrent calls to @a pthreadpool_parallelize_* from different threads. + */ + dispatch_semaphore_t execution_semaphore; +#endif +#if PTHREADPOOL_USE_EVENT + /** + * Serializes concurrent calls to @a pthreadpool_parallelize_* from different threads. + */ + HANDLE execution_mutex; +#endif +#if PTHREADPOOL_USE_CONDVAR + /** + * Guards access to the @a active_threads variable. + */ + pthread_mutex_t completion_mutex; + /** + * Condition variable to wait until all threads complete an operation (until @a active_threads is zero). + */ + pthread_cond_t completion_condvar; + /** + * Guards access to the @a command variable. + */ + pthread_mutex_t command_mutex; + /** + * Condition variable to wait for change of the @a command variable. + */ + pthread_cond_t command_condvar; +#endif +#if PTHREADPOOL_USE_EVENT + /** + * Events to wait on until all threads complete an operation (until @a active_threads is zero). + * To avoid race conditions due to spin-lock synchronization, we use two events and switch event in use after every + * submitted command according to the high bit of the command word. + */ + HANDLE completion_event[2]; + /** + * Events to wait on for change of the @a command variable. + * To avoid race conditions due to spin-lock synchronization, we use two events and switch event in use after every + * submitted command according to the high bit of the command word. + */ + HANDLE command_event[2]; +#endif + /** + * FXdiv divisor for the number of threads in the thread pool. + * This struct never change after pthreadpool_create. + */ + struct fxdiv_divisor_size_t threads_count; + /** + * Thread information structures that immediately follow this structure. + */ + struct thread_info threads[]; +}; + +PTHREADPOOL_STATIC_ASSERT(sizeof(struct pthreadpool) % PTHREADPOOL_CACHELINE_SIZE == 0, + "pthreadpool structure must occupy an integer number of cache lines (64 bytes)"); + +PTHREADPOOL_INTERNAL struct pthreadpool* pthreadpool_allocate( + size_t threads_count); + +PTHREADPOOL_INTERNAL void pthreadpool_deallocate( + struct pthreadpool* threadpool); + +typedef void (*thread_function_t)(struct pthreadpool* threadpool, struct thread_info* thread); + +PTHREADPOOL_INTERNAL void pthreadpool_parallelize( + struct pthreadpool* threadpool, + thread_function_t thread_function, + const void* params, + size_t params_size, + void* task, + void* context, + size_t linear_range, + uint32_t flags); diff --git a/src/threadpool-pthreads.c b/src/threadpool-pthreads.c deleted file mode 100644 index 0a9c06d..0000000 --- a/src/threadpool-pthreads.c +++ /dev/null @@ -1,1702 +0,0 @@ -/* Standard C headers */ -#include <assert.h> -#include <stdbool.h> -#include <stdint.h> -#include <stdlib.h> -#include <string.h> - -/* POSIX headers */ -#include <pthread.h> -#include <unistd.h> - -#ifndef PTHREADPOOL_USE_CPUINFO - #define PTHREADPOOL_USE_CPUINFO 0 -#endif - -#ifndef PTHREADPOOL_USE_FUTEX - #if defined(__linux__) - #define PTHREADPOOL_USE_FUTEX 1 - #elif defined(__EMSCRIPTEN__) - #define PTHREADPOOL_USE_FUTEX 1 - #else - #define PTHREADPOOL_USE_FUTEX 0 - #endif -#endif - -#if PTHREADPOOL_USE_CPUINFO - #include <cpuinfo.h> -#endif - -/* Futex-specific headers */ -#if PTHREADPOOL_USE_FUTEX - #if defined(__linux__) - #include <sys/syscall.h> - #include <linux/futex.h> - - /* Old Android NDKs do not define SYS_futex and FUTEX_PRIVATE_FLAG */ - #ifndef SYS_futex - #define SYS_futex __NR_futex - #endif - #ifndef FUTEX_PRIVATE_FLAG - #define FUTEX_PRIVATE_FLAG 128 - #endif - #elif defined(__EMSCRIPTEN__) - /* math.h for INFINITY constant */ - #include <math.h> - - #include <emscripten/threading.h> - #else - #error "Platform-specific implementation of futex_wait and futex_wake_all required" - #endif -#endif - -#ifdef _WIN32 - #define NOMINMAX - #include <malloc.h> - #include <sysinfoapi.h> -#endif - -/* Dependencies */ -#include <fxdiv.h> - -/* Library header */ -#include <pthreadpool.h> - -/* Internal headers */ -#include "threadpool-utils.h" -#include "threadpool-atomics.h" - -/* Number of iterations in spin-wait loop before going into futex/mutex wait */ -#define PTHREADPOOL_SPIN_WAIT_ITERATIONS 1000000 - -#define PTHREADPOOL_CACHELINE_SIZE 64 -#define PTHREADPOOL_CACHELINE_ALIGNED __attribute__((__aligned__(PTHREADPOOL_CACHELINE_SIZE))) - -#if defined(__clang__) - #if __has_extension(c_static_assert) || __has_feature(c_static_assert) - #define PTHREADPOOL_STATIC_ASSERT(predicate, message) _Static_assert((predicate), message) - #else - #define PTHREADPOOL_STATIC_ASSERT(predicate, message) - #endif -#elif defined(__GNUC__) && ((__GNUC__ > 4) || (__GNUC__ == 4) && (__GNUC_MINOR__ >= 6)) - /* Static assert is supported by gcc >= 4.6 */ - #define PTHREADPOOL_STATIC_ASSERT(predicate, message) _Static_assert((predicate), message) -#else - #define PTHREADPOOL_STATIC_ASSERT(predicate, message) -#endif - -static inline size_t multiply_divide(size_t a, size_t b, size_t d) { - #if defined(__SIZEOF_SIZE_T__) && (__SIZEOF_SIZE_T__ == 4) - return (size_t) (((uint64_t) a) * ((uint64_t) b)) / ((uint64_t) d); - #elif defined(__SIZEOF_SIZE_T__) && (__SIZEOF_SIZE_T__ == 8) - return (size_t) (((__uint128_t) a) * ((__uint128_t) b)) / ((__uint128_t) d); - #else - #error "Unsupported platform" - #endif -} - -static inline size_t divide_round_up(size_t dividend, size_t divisor) { - if (dividend % divisor == 0) { - return dividend / divisor; - } else { - return dividend / divisor + 1; - } -} - -static inline size_t min(size_t a, size_t b) { - return a < b ? a : b; -} - -#if PTHREADPOOL_USE_FUTEX - #if defined(__linux__) - static int futex_wait(pthreadpool_atomic_uint32_t* address, uint32_t value) { - return syscall(SYS_futex, address, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, value, NULL); - } - - static int futex_wake_all(pthreadpool_atomic_uint32_t* address) { - return syscall(SYS_futex, address, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT_MAX); - } - #elif defined(__EMSCRIPTEN__) - static int futex_wait(pthreadpool_atomic_uint32_t* address, uint32_t value) { - return emscripten_futex_wait((volatile void*) address, value, INFINITY); - } - - static int futex_wake_all(pthreadpool_atomic_uint32_t* address) { - return emscripten_futex_wake((volatile void*) address, INT_MAX); - } - #else - #error "Platform-specific implementation of futex_wait and futex_wake_all required" - #endif -#endif - -#define THREADPOOL_COMMAND_MASK UINT32_C(0x7FFFFFFF) - -enum threadpool_command { - threadpool_command_init, - threadpool_command_parallelize, - threadpool_command_shutdown, -}; - -struct PTHREADPOOL_CACHELINE_ALIGNED thread_info { - /** - * Index of the first element in the work range. - * Before processing a new element the owning worker thread increments this value. - */ - pthreadpool_atomic_size_t range_start; - /** - * Index of the element after the last element of the work range. - * Before processing a new element the stealing worker thread decrements this value. - */ - pthreadpool_atomic_size_t range_end; - /** - * The number of elements in the work range. - * Due to race conditions range_length <= range_end - range_start. - * The owning worker thread must decrement this value before incrementing @a range_start. - * The stealing worker thread must decrement this value before decrementing @a range_end. - */ - pthreadpool_atomic_size_t range_length; - /** - * Thread number in the 0..threads_count-1 range. - */ - size_t thread_number; - /** - * The pthread object corresponding to the thread. - */ - pthread_t thread_object; - /** - * Condition variable used to wake up the thread. - * When the thread is idle, it waits on this condition variable. - */ - pthread_cond_t wakeup_condvar; -}; - -PTHREADPOOL_STATIC_ASSERT(sizeof(struct thread_info) % PTHREADPOOL_CACHELINE_SIZE == 0, "thread_info structure must occupy an integer number of cache lines (64 bytes)"); - -struct pthreadpool_1d_with_uarch_params { - /** - * Copy of the default uarch index argument passed to a microarchitecture-aware parallelization function. - */ - uint32_t default_uarch_index; - /** - * Copy of the max uarch index argument passed to a microarchitecture-aware parallelization function. - */ - uint32_t max_uarch_index; -}; - -struct PTHREADPOOL_CACHELINE_ALIGNED pthreadpool { - /** - * The number of threads that are processing an operation. - */ - pthreadpool_atomic_size_t active_threads; -#if PTHREADPOOL_USE_FUTEX - /** - * Indicates if there are active threads. - * Only two values are possible: - * - has_active_threads == 0 if active_threads == 0 - * - has_active_threads == 1 if active_threads != 0 - */ - pthreadpool_atomic_uint32_t has_active_threads; -#endif - /** - * The last command submitted to the thread pool. - */ - pthreadpool_atomic_uint32_t command; - /** - * The entry point function to call for each thread in the thread pool for parallelization tasks. - */ - pthreadpool_atomic_void_p thread_function; - /** - * The function to call for each item. - */ - pthreadpool_atomic_void_p task; - /** - * The first argument to the item processing function. - */ - pthreadpool_atomic_void_p argument; - /** - * Additional parallelization parameters. - * These parameters are specific for each thread_function. - */ - union { - struct pthreadpool_1d_with_uarch_params parallelize_1d_with_uarch; - } params; - /** - * Copy of the flags passed to a parallelization function. - */ - pthreadpool_atomic_uint32_t flags; - /** - * Serializes concurrent calls to @a pthreadpool_parallelize_* from different threads. - */ - pthread_mutex_t execution_mutex; -#if !PTHREADPOOL_USE_FUTEX - /** - * Guards access to the @a active_threads variable. - */ - pthread_mutex_t completion_mutex; - /** - * Condition variable to wait until all threads complete an operation (until @a active_threads is zero). - */ - pthread_cond_t completion_condvar; - /** - * Guards access to the @a command variable. - */ - pthread_mutex_t command_mutex; - /** - * Condition variable to wait for change of the @a command variable. - */ - pthread_cond_t command_condvar; -#endif -#if PTHREADPOOL_USE_CPUINFO - /** - * Indication whether cpuinfo library initialized successfully. Never changes after pthreadpool_create. - */ - bool cpuinfo_is_initialized; -#endif - /** - * The number of threads in the thread pool. Never changes after pthreadpool_create. - */ - size_t threads_count; - /** - * Thread information structures that immediately follow this structure. - */ - struct thread_info threads[]; -}; - -PTHREADPOOL_STATIC_ASSERT(sizeof(struct pthreadpool) % PTHREADPOOL_CACHELINE_SIZE == 0, "pthreadpool structure must occupy an integer number of cache lines (64 bytes)"); - -static void checkin_worker_thread(struct pthreadpool* threadpool) { - #if PTHREADPOOL_USE_FUTEX - if (pthreadpool_fetch_sub_relaxed_size_t(&threadpool->active_threads, 1) == 1) { - pthreadpool_store_relaxed_uint32_t(&threadpool->has_active_threads, 0); - futex_wake_all(&threadpool->has_active_threads); - } - #else - pthread_mutex_lock(&threadpool->completion_mutex); - if (pthreadpool_fetch_sub_relaxed_size_t(&threadpool->active_threads, 1) == 1) { - pthread_cond_signal(&threadpool->completion_condvar); - } - pthread_mutex_unlock(&threadpool->completion_mutex); - #endif -} - -static void wait_worker_threads(struct pthreadpool* threadpool) { - /* Initial check */ - #if PTHREADPOOL_USE_FUTEX - uint32_t has_active_threads = pthreadpool_load_relaxed_uint32_t(&threadpool->has_active_threads); - if (has_active_threads == 0) { - return; - } - #else - size_t active_threads = pthreadpool_load_relaxed_size_t(&threadpool->active_threads); - if (active_threads == 0) { - return; - } - #endif - - /* Spin-wait */ - for (uint32_t i = PTHREADPOOL_SPIN_WAIT_ITERATIONS; i != 0; i--) { - /* This fence serves as a sleep instruction */ - pthreadpool_fence_acquire(); - - #if PTHREADPOOL_USE_FUTEX - has_active_threads = pthreadpool_load_relaxed_uint32_t(&threadpool->has_active_threads); - if (has_active_threads == 0) { - return; - } - #else - active_threads = pthreadpool_load_relaxed_size_t(&threadpool->active_threads); - if (active_threads == 0) { - return; - } - #endif - } - - /* Fall-back to mutex/futex wait */ - #if PTHREADPOOL_USE_FUTEX - while ((has_active_threads = pthreadpool_load_relaxed_uint32_t(&threadpool->has_active_threads)) != 0) { - futex_wait(&threadpool->has_active_threads, 1); - } - #else - pthread_mutex_lock(&threadpool->completion_mutex); - while (pthreadpool_load_relaxed_size_t(&threadpool->active_threads) != 0) { - pthread_cond_wait(&threadpool->completion_condvar, &threadpool->completion_mutex); - }; - pthread_mutex_unlock(&threadpool->completion_mutex); - #endif -} - -inline static bool atomic_decrement(pthreadpool_atomic_size_t* value) { - #if defined(__clang__) && (defined(__arm__) || defined(__aarch64__)) - size_t actual_value; - do { - actual_value = __builtin_arm_ldrex((const volatile size_t*) value); - if (actual_value == 0) { - __builtin_arm_clrex(); - return false; - } - } while (__builtin_arm_strex(actual_value - 1, (volatile size_t*) value) != 0); - return true; - #else - size_t actual_value = pthreadpool_load_relaxed_size_t(value); - if (actual_value == 0) { - return false; - } - while (!pthreadpool_compare_exchange_weak_relaxed_size_t(value, &actual_value, actual_value - 1)) { - if (actual_value == 0) { - return false; - } - } - return true; - #endif -} - -inline static size_t modulo_decrement(uint32_t i, uint32_t n) { - /* Wrap modulo n, if needed */ - if (i == 0) { - i = n; - } - /* Decrement input variable */ - return i - 1; -} - -typedef void (*thread_function_t)(struct pthreadpool* threadpool, struct thread_info* thread); - -static void thread_parallelize_1d(struct pthreadpool* threadpool, struct thread_info* thread) { - const pthreadpool_task_1d_t task = (pthreadpool_task_1d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); - void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); - /* Process thread's own range of items */ - size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); - while (atomic_decrement(&thread->range_length)) { - task(argument, range_start++); - } - - /* There still may be other threads with work */ - const size_t thread_number = thread->thread_number; - const size_t threads_count = threadpool->threads_count; - for (size_t tid = modulo_decrement(thread_number, threads_count); - tid != thread_number; - tid = modulo_decrement(tid, threads_count)) - { - struct thread_info* other_thread = &threadpool->threads[tid]; - while (atomic_decrement(&other_thread->range_length)) { - const size_t item_id = pthreadpool_fetch_sub_relaxed_size_t(&other_thread->range_end, 1) - 1; - task(argument, item_id); - } - } - - /* Make changes by this thread visible to other threads */ - pthreadpool_fence_release(); -} - -static void thread_parallelize_1d_with_uarch(struct pthreadpool* threadpool, struct thread_info* thread) { - const pthreadpool_task_1d_with_id_t task = (pthreadpool_task_1d_with_id_t) pthreadpool_load_relaxed_void_p(&threadpool->task); - void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); - - const uint32_t default_uarch_index = threadpool->params.parallelize_1d_with_uarch.default_uarch_index; - uint32_t uarch_index = default_uarch_index; - #if PTHREADPOOL_USE_CPUINFO - if (threadpool && threadpool->cpuinfo_is_initialized) { - uarch_index = cpuinfo_get_current_uarch_index(); - if (uarch_index > threadpool->params.parallelize_1d_with_uarch.max_uarch_index) { - uarch_index = default_uarch_index; - } - } - #endif - - /* Process thread's own range of items */ - size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); - while (atomic_decrement(&thread->range_length)) { - task(argument, uarch_index, range_start++); - } - - /* There still may be other threads with work */ - const size_t thread_number = thread->thread_number; - const size_t threads_count = threadpool->threads_count; - for (size_t tid = modulo_decrement(thread_number, threads_count); - tid != thread_number; - tid = modulo_decrement(tid, threads_count)) - { - struct thread_info* other_thread = &threadpool->threads[tid]; - while (atomic_decrement(&other_thread->range_length)) { - const size_t item_id = pthreadpool_fetch_sub_relaxed_size_t(&other_thread->range_end, 1) - 1; - task(argument, uarch_index, item_id); - } - } - - /* Make changes by this thread visible to other threads */ - pthreadpool_fence_release(); -} - -static uint32_t wait_for_new_command( - struct pthreadpool* threadpool, - uint32_t last_command, - uint32_t last_flags) -{ - uint32_t command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); - if (command != last_command) { - return command; - } - - if ((last_flags & PTHREADPOOL_FLAG_YIELD_WORKERS) == 0) { - /* Spin-wait loop */ - for (uint32_t i = PTHREADPOOL_SPIN_WAIT_ITERATIONS; i != 0; i--) { - /* This fence serves as a sleep instruction */ - pthreadpool_fence_acquire(); - - command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); - if (command != last_command) { - return command; - } - } - } - - /* Spin-wait disabled or timed out, fall back to mutex/futex wait */ - #if PTHREADPOOL_USE_FUTEX - do { - futex_wait(&threadpool->command, last_command); - command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); - } while (command == last_command); - #else - /* Lock the command mutex */ - pthread_mutex_lock(&threadpool->command_mutex); - /* Read the command */ - while ((command = pthreadpool_load_relaxed_uint32_t(&threadpool->command)) == last_command) { - /* Wait for new command */ - pthread_cond_wait(&threadpool->command_condvar, &threadpool->command_mutex); - } - /* Read a new command */ - pthread_mutex_unlock(&threadpool->command_mutex); - #endif - return command; -} - -static void* thread_main(void* arg) { - struct thread_info* thread = (struct thread_info*) arg; - struct pthreadpool* threadpool = ((struct pthreadpool*) (thread - thread->thread_number)) - 1; - uint32_t last_command = threadpool_command_init; - struct fpu_state saved_fpu_state = { 0 }; - uint32_t flags = 0; - - /* Check in */ - checkin_worker_thread(threadpool); - - /* Monitor new commands and act accordingly */ - for (;;) { - uint32_t command = wait_for_new_command(threadpool, last_command, flags); - pthreadpool_fence_acquire(); - - flags = pthreadpool_load_relaxed_uint32_t(&threadpool->flags); - - /* Process command */ - switch (command & THREADPOOL_COMMAND_MASK) { - case threadpool_command_parallelize: - { - const thread_function_t thread_function = - (thread_function_t) pthreadpool_load_relaxed_void_p(&threadpool->thread_function); - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - - thread_function(threadpool, thread); - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - break; - } - case threadpool_command_shutdown: - /* Exit immediately: the master thread is waiting on pthread_join */ - return NULL; - case threadpool_command_init: - /* To inhibit compiler warning */ - break; - } - /* Notify the master thread that we finished processing */ - checkin_worker_thread(threadpool); - /* Update last command */ - last_command = command; - }; -} - -static struct pthreadpool* pthreadpool_allocate(size_t threads_count) { - const size_t threadpool_size = sizeof(struct pthreadpool) + threads_count * sizeof(struct thread_info); - struct pthreadpool* threadpool = NULL; - #if defined(__ANDROID__) - /* - * Android didn't get posix_memalign until API level 17 (Android 4.2). - * Use (otherwise obsolete) memalign function on Android platform. - */ - threadpool = memalign(PTHREADPOOL_CACHELINE_SIZE, threadpool_size); - if (threadpool == NULL) { - return NULL; - } - #elif defined(_WIN32) - threadpool = _aligned_malloc(threadpool_size, PTHREADPOOL_CACHELINE_SIZE); - if (threadpool == NULL) { - return NULL; - } - #else - if (posix_memalign((void**) &threadpool, PTHREADPOOL_CACHELINE_SIZE, threadpool_size) != 0) { - return NULL; - } - #endif - memset(threadpool, 0, threadpool_size); - return threadpool; -} - -struct pthreadpool* pthreadpool_create(size_t threads_count) { - if (threads_count == 0) { - #if defined(_SC_NPROCESSORS_ONLN) - threads_count = (size_t) sysconf(_SC_NPROCESSORS_ONLN); - #if defined(__EMSCRIPTEN_PTHREADS__) - /* Limit the number of threads to 8 to match link-time PTHREAD_POOL_SIZE option */ - if (threads_count >= 8) { - threads_count = 8; - } - #endif - #elif defined(_WIN32) - SYSTEM_INFO system_info; - ZeroMemory(&system_info, sizeof(system_info)); - GetSystemInfo(&system_info); - threads_count = (size_t) system_info.dwNumberOfProcessors; - #else - #error "Unsupported platform" - #endif - } - - struct pthreadpool* threadpool = pthreadpool_allocate(threads_count); - if (threadpool == NULL) { - return NULL; - } - threadpool->threads_count = threads_count; - for (size_t tid = 0; tid < threads_count; tid++) { - threadpool->threads[tid].thread_number = tid; - } - #if PTHREADPOOL_USE_CPUINFO - threadpool->cpuinfo_is_initialized = cpuinfo_initialize(); - #endif - - /* Thread pool with a single thread computes everything on the caller thread. */ - if (threads_count > 1) { - pthread_mutex_init(&threadpool->execution_mutex, NULL); - #if !PTHREADPOOL_USE_FUTEX - pthread_mutex_init(&threadpool->completion_mutex, NULL); - pthread_cond_init(&threadpool->completion_condvar, NULL); - pthread_mutex_init(&threadpool->command_mutex, NULL); - pthread_cond_init(&threadpool->command_condvar, NULL); - #endif - - #if PTHREADPOOL_USE_FUTEX - pthreadpool_store_relaxed_uint32_t(&threadpool->has_active_threads, 1); - #endif - pthreadpool_store_release_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); - - /* Caller thread serves as worker #0. Thus, we create system threads starting with worker #1. */ - for (size_t tid = 1; tid < threads_count; tid++) { - pthread_create(&threadpool->threads[tid].thread_object, NULL, &thread_main, &threadpool->threads[tid]); - } - - /* Wait until all threads initialize */ - wait_worker_threads(threadpool); - } - return threadpool; -} - -size_t pthreadpool_get_threads_count(struct pthreadpool* threadpool) { - if (threadpool == NULL) { - return 1; - } else { - return threadpool->threads_count; - } -} - -static void pthreadpool_parallelize( - struct pthreadpool* threadpool, - thread_function_t thread_function, - const void* params, - size_t params_size, - void* task, - void* context, - size_t linear_range, - uint32_t flags) -{ - assert(threadpool != NULL); - assert(thread_function != NULL); - assert(task != NULL); - assert(linear_range > 1); - - /* Protect the global threadpool structures */ - pthread_mutex_lock(&threadpool->execution_mutex); - - #if !PTHREADPOOL_USE_FUTEX - /* Lock the command variables to ensure that threads don't start processing before they observe complete command with all arguments */ - pthread_mutex_lock(&threadpool->command_mutex); - #endif - - /* Setup global arguments */ - pthreadpool_store_relaxed_void_p(&threadpool->thread_function, (void*) thread_function); - pthreadpool_store_relaxed_void_p(&threadpool->task, task); - pthreadpool_store_relaxed_void_p(&threadpool->argument, context); - pthreadpool_store_relaxed_uint32_t(&threadpool->flags, flags); - - /* Locking of completion_mutex not needed: readers are sleeping on command_condvar */ - const size_t threads_count = threadpool->threads_count; - pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); - #if PTHREADPOOL_USE_FUTEX - pthreadpool_store_relaxed_uint32_t(&threadpool->has_active_threads, 1); - #endif - - if (params_size != 0) { - memcpy(&threadpool->params, params, params_size); - pthreadpool_fence_release(); - } - - /* Spread the work between threads */ - size_t range_start = 0; - for (size_t tid = 0; tid < threads_count; tid++) { - struct thread_info* thread = &threadpool->threads[tid]; - const size_t range_end = multiply_divide(linear_range, tid + 1, threads_count); - pthreadpool_store_relaxed_size_t(&thread->range_start, range_start); - pthreadpool_store_relaxed_size_t(&thread->range_end, range_end); - pthreadpool_store_relaxed_size_t(&thread->range_length, range_end - range_start); - - /* The next subrange starts where the previous ended */ - range_start = range_end; - } - - /* - * Update the threadpool command. - * Imporantly, do it after initializing command parameters (range, task, argument, flags) - * ~(threadpool->command | THREADPOOL_COMMAND_MASK) flips the bits not in command mask - * to ensure the unmasked command is different then the last command, because worker threads - * monitor for change in the unmasked command. - */ - const uint32_t old_command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); - const uint32_t new_command = ~(old_command | THREADPOOL_COMMAND_MASK) | threadpool_command_parallelize; - - /* - * Store the command with release semantics to guarantee that if a worker thread observes - * the new command value, it also observes the updated command parameters. - * - * Note: release semantics is necessary even with a conditional variable, because the workers might - * be waiting in a spin-loop rather than the conditional variable. - */ - pthreadpool_store_release_uint32_t(&threadpool->command, new_command); - #if PTHREADPOOL_USE_FUTEX - /* Wake up the threads */ - futex_wake_all(&threadpool->command); - #else - /* Unlock the command variables before waking up the threads for better performance */ - pthread_mutex_unlock(&threadpool->command_mutex); - - /* Wake up the threads */ - pthread_cond_broadcast(&threadpool->command_condvar); - #endif - - /* Save and modify FPU denormals control, if needed */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - - /* Do computations as worker #0 */ - thread_function(threadpool, &threadpool->threads[0]); - - /* Restore FPU denormals control, if needed */ - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - - /* Wait until the threads finish computation */ - wait_worker_threads(threadpool); - - /* Make changes by other threads visible to this thread */ - pthreadpool_fence_acquire(); - - /* Unprotect the global threadpool structures */ - pthread_mutex_unlock(&threadpool->execution_mutex); -} - -void pthreadpool_parallelize_1d( - struct pthreadpool* threadpool, - pthreadpool_task_1d_t task, - void* argument, - size_t range, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || range <= 1) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range; i++) { - task(argument, i); - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) task, argument, range, flags); - } -} - -void pthreadpool_parallelize_1d_with_uarch( - pthreadpool_t threadpool, - pthreadpool_task_1d_with_id_t task, - void* argument, - uint32_t default_uarch_index, - uint32_t max_uarch_index, - size_t range, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || range <= 1) { - /* No thread pool used: execute task sequentially on the calling thread */ - - uint32_t uarch_index = default_uarch_index; - #if PTHREADPOOL_USE_CPUINFO - if (threadpool && threadpool->cpuinfo_is_initialized) { - uarch_index = cpuinfo_get_current_uarch_index(); - if (uarch_index > max_uarch_index) { - uarch_index = default_uarch_index; - } - } - #endif - - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range; i++) { - task(argument, uarch_index, i); - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - const struct pthreadpool_1d_with_uarch_params params = { - .default_uarch_index = default_uarch_index, - .max_uarch_index = max_uarch_index, - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d_with_uarch, ¶ms, sizeof(params), - task, argument, range, flags); - } -} - -struct compute_1d_tile_1d_context { - pthreadpool_task_1d_tile_1d_t task; - void* argument; - size_t range; - size_t tile; -}; - -static void compute_1d_tile_1d(const struct compute_1d_tile_1d_context* context, size_t linear_index) { - const size_t tile_index = linear_index; - const size_t index = tile_index * context->tile; - const size_t tile = min(context->tile, context->range - index); - context->task(context->argument, index, tile); -} - -void pthreadpool_parallelize_1d_tile_1d( - pthreadpool_t threadpool, - pthreadpool_task_1d_tile_1d_t task, - void* argument, - size_t range, - size_t tile, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || range <= tile) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range; i += tile) { - task(argument, i, min(range - i, tile)); - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range = divide_round_up(range, tile); - struct compute_1d_tile_1d_context context = { - .task = task, - .argument = argument, - .range = range, - .tile = tile - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_1d_tile_1d, &context, tile_range, flags); - } -} - -struct compute_2d_context { - pthreadpool_task_2d_t task; - void* argument; - struct fxdiv_divisor_size_t range_j; -}; - -static void compute_2d(const struct compute_2d_context* context, size_t linear_index) { - const struct fxdiv_divisor_size_t range_j = context->range_j; - const struct fxdiv_result_size_t index = fxdiv_divide_size_t(linear_index, range_j); - context->task(context->argument, index.quotient, index.remainder); -} - -void pthreadpool_parallelize_2d( - struct pthreadpool* threadpool, - pthreadpool_task_2d_t task, - void* argument, - size_t range_i, - size_t range_j, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || (range_i | range_j) <= 1) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j++) { - task(argument, i, j); - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - struct compute_2d_context context = { - .task = task, - .argument = argument, - .range_j = fxdiv_init_size_t(range_j) - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_2d, &context, range_i * range_j, flags); - } -} - -struct compute_2d_tile_1d_context { - pthreadpool_task_2d_tile_1d_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_j; - size_t range_i; - size_t range_j; - size_t tile_j; -}; - -static void compute_2d_tile_1d(const struct compute_2d_tile_1d_context* context, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_j = context->tile_range_j; - const struct fxdiv_result_size_t tile_index = fxdiv_divide_size_t(linear_index, tile_range_j); - const size_t max_tile_j = context->tile_j; - const size_t index_i = tile_index.quotient; - const size_t index_j = tile_index.remainder * max_tile_j; - const size_t tile_j = min(max_tile_j, context->range_j - index_j); - context->task(context->argument, index_i, index_j, tile_j); -} - -void pthreadpool_parallelize_2d_tile_1d( - pthreadpool_t threadpool, - pthreadpool_task_2d_tile_1d_t task, - void* argument, - size_t range_i, - size_t range_j, - size_t tile_j, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || (range_i <= 1 && range_j <= tile_j)) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j += tile_j) { - task(argument, i, j, min(range_j - j, tile_j)); - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_j = divide_round_up(range_j, tile_j); - struct compute_2d_tile_1d_context context = { - .task = task, - .argument = argument, - .tile_range_j = fxdiv_init_size_t(tile_range_j), - .range_i = range_i, - .range_j = range_j, - .tile_j = tile_j - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_2d_tile_1d, &context, range_i * tile_range_j, flags); - } -} - -struct compute_2d_tile_2d_context { - pthreadpool_task_2d_tile_2d_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_j; - size_t range_i; - size_t range_j; - size_t tile_i; - size_t tile_j; -}; - -static void compute_2d_tile_2d(const struct compute_2d_tile_2d_context* context, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_j = context->tile_range_j; - const struct fxdiv_result_size_t tile_index = fxdiv_divide_size_t(linear_index, tile_range_j); - const size_t max_tile_i = context->tile_i; - const size_t max_tile_j = context->tile_j; - const size_t index_i = tile_index.quotient * max_tile_i; - const size_t index_j = tile_index.remainder * max_tile_j; - const size_t tile_i = min(max_tile_i, context->range_i - index_i); - const size_t tile_j = min(max_tile_j, context->range_j - index_j); - context->task(context->argument, index_i, index_j, tile_i, tile_j); -} - -void pthreadpool_parallelize_2d_tile_2d( - pthreadpool_t threadpool, - pthreadpool_task_2d_tile_2d_t task, - void* argument, - size_t range_i, - size_t range_j, - size_t tile_i, - size_t tile_j, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || (range_i <= tile_i && range_j <= tile_j)) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i += tile_i) { - for (size_t j = 0; j < range_j; j += tile_j) { - task(argument, i, j, min(range_i - i, tile_i), min(range_j - j, tile_j)); - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_i = divide_round_up(range_i, tile_i); - const size_t tile_range_j = divide_round_up(range_j, tile_j); - struct compute_2d_tile_2d_context context = { - .task = task, - .argument = argument, - .tile_range_j = fxdiv_init_size_t(tile_range_j), - .range_i = range_i, - .range_j = range_j, - .tile_i = tile_i, - .tile_j = tile_j - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_2d_tile_2d, &context, tile_range_i * tile_range_j, flags); - } -} - -struct compute_2d_tile_2d_with_uarch_context { - pthreadpool_task_2d_tile_2d_with_id_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_j; - size_t range_i; - size_t range_j; - size_t tile_i; - size_t tile_j; -}; - -static void compute_2d_tile_2d_with_uarch(const struct compute_2d_tile_2d_with_uarch_context* context, uint32_t uarch_index, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_j = context->tile_range_j; - const struct fxdiv_result_size_t tile_index = fxdiv_divide_size_t(linear_index, tile_range_j); - const size_t max_tile_i = context->tile_i; - const size_t max_tile_j = context->tile_j; - const size_t index_i = tile_index.quotient * max_tile_i; - const size_t index_j = tile_index.remainder * max_tile_j; - const size_t tile_i = min(max_tile_i, context->range_i - index_i); - const size_t tile_j = min(max_tile_j, context->range_j - index_j); - context->task(context->argument, uarch_index, index_i, index_j, tile_i, tile_j); -} - -void pthreadpool_parallelize_2d_tile_2d_with_uarch( - pthreadpool_t threadpool, - pthreadpool_task_2d_tile_2d_with_id_t task, - void* argument, - uint32_t default_uarch_index, - uint32_t max_uarch_index, - size_t range_i, - size_t range_j, - size_t tile_i, - size_t tile_j, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || (range_i <= tile_i && range_j <= tile_j)) { - /* No thread pool used: execute task sequentially on the calling thread */ - - uint32_t uarch_index = default_uarch_index; - #if PTHREADPOOL_USE_CPUINFO - if (threadpool && threadpool->cpuinfo_is_initialized) { - uarch_index = cpuinfo_get_current_uarch_index(); - if (uarch_index > max_uarch_index) { - uarch_index = default_uarch_index; - } - } - #endif - - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i += tile_i) { - for (size_t j = 0; j < range_j; j += tile_j) { - task(argument, uarch_index, i, j, min(range_i - i, tile_i), min(range_j - j, tile_j)); - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_i = divide_round_up(range_i, tile_i); - const size_t tile_range_j = divide_round_up(range_j, tile_j); - const struct pthreadpool_1d_with_uarch_params params = { - .default_uarch_index = default_uarch_index, - .max_uarch_index = max_uarch_index, - }; - struct compute_2d_tile_2d_with_uarch_context context = { - .task = task, - .argument = argument, - .tile_range_j = fxdiv_init_size_t(tile_range_j), - .range_i = range_i, - .range_j = range_j, - .tile_i = tile_i, - .tile_j = tile_j - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d_with_uarch, ¶ms, sizeof(params), - (void*) compute_2d_tile_2d_with_uarch, &context, tile_range_i * tile_range_j, flags); - } -} - -struct compute_3d_tile_2d_context { - pthreadpool_task_3d_tile_2d_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_j; - struct fxdiv_divisor_size_t tile_range_k; - size_t range_j; - size_t range_k; - size_t tile_j; - size_t tile_k; -}; - -static void compute_3d_tile_2d(const struct compute_3d_tile_2d_context* context, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_k = context->tile_range_k; - const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(linear_index, tile_range_k); - const struct fxdiv_divisor_size_t tile_range_j = context->tile_range_j; - const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, tile_range_j); - const size_t max_tile_j = context->tile_j; - const size_t max_tile_k = context->tile_k; - const size_t index_i = tile_index_i_j.quotient; - const size_t index_j = tile_index_i_j.remainder * max_tile_j; - const size_t index_k = tile_index_ij_k.remainder * max_tile_k; - const size_t tile_j = min(max_tile_j, context->range_j - index_j); - const size_t tile_k = min(max_tile_k, context->range_k - index_k); - context->task(context->argument, index_i, index_j, index_k, tile_j, tile_k); -} - -void pthreadpool_parallelize_3d_tile_2d( - pthreadpool_t threadpool, - pthreadpool_task_3d_tile_2d_t task, - void* argument, - size_t range_i, - size_t range_j, - size_t range_k, - size_t tile_j, - size_t tile_k, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || (range_i <= 1 && range_j <= tile_j && range_k <= tile_k)) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j += tile_j) { - for (size_t k = 0; k < range_k; k += tile_k) { - task(argument, i, j, k, min(range_j - j, tile_j), min(range_k - k, tile_k)); - } - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_j = divide_round_up(range_j, tile_j); - const size_t tile_range_k = divide_round_up(range_k, tile_k); - struct compute_3d_tile_2d_context context = { - .task = task, - .argument = argument, - .tile_range_j = fxdiv_init_size_t(tile_range_j), - .tile_range_k = fxdiv_init_size_t(tile_range_k), - .range_j = range_j, - .range_k = range_k, - .tile_j = tile_j, - .tile_k = tile_k - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_3d_tile_2d, &context, range_i * tile_range_j * tile_range_k, flags); - } -} - -struct compute_3d_tile_2d_with_uarch_context { - pthreadpool_task_3d_tile_2d_with_id_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_j; - struct fxdiv_divisor_size_t tile_range_k; - size_t range_j; - size_t range_k; - size_t tile_j; - size_t tile_k; -}; - -static void compute_3d_tile_2d_with_uarch(const struct compute_3d_tile_2d_with_uarch_context* context, uint32_t uarch_index, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_k = context->tile_range_k; - const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(linear_index, tile_range_k); - const struct fxdiv_divisor_size_t tile_range_j = context->tile_range_j; - const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, tile_range_j); - const size_t max_tile_j = context->tile_j; - const size_t max_tile_k = context->tile_k; - const size_t index_i = tile_index_i_j.quotient; - const size_t index_j = tile_index_i_j.remainder * max_tile_j; - const size_t index_k = tile_index_ij_k.remainder * max_tile_k; - const size_t tile_j = min(max_tile_j, context->range_j - index_j); - const size_t tile_k = min(max_tile_k, context->range_k - index_k); - context->task(context->argument, uarch_index, index_i, index_j, index_k, tile_j, tile_k); -} - -void pthreadpool_parallelize_3d_tile_2d_with_uarch( - pthreadpool_t threadpool, - pthreadpool_task_3d_tile_2d_with_id_t task, - void* argument, - uint32_t default_uarch_index, - uint32_t max_uarch_index, - size_t range_i, - size_t range_j, - size_t range_k, - size_t tile_j, - size_t tile_k, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || (range_i <= 1 && range_j <= tile_j && range_k <= tile_k)) { - /* No thread pool used: execute task sequentially on the calling thread */ - - uint32_t uarch_index = default_uarch_index; - #if PTHREADPOOL_USE_CPUINFO - if (threadpool && threadpool->cpuinfo_is_initialized) { - uarch_index = cpuinfo_get_current_uarch_index(); - if (uarch_index > max_uarch_index) { - uarch_index = default_uarch_index; - } - } - #endif - - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j += tile_j) { - for (size_t k = 0; k < range_k; k += tile_k) { - task(argument, uarch_index, i, j, k, min(range_j - j, tile_j), min(range_k - k, tile_k)); - } - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_j = divide_round_up(range_j, tile_j); - const size_t tile_range_k = divide_round_up(range_k, tile_k); - const struct pthreadpool_1d_with_uarch_params params = { - .default_uarch_index = default_uarch_index, - .max_uarch_index = max_uarch_index, - }; - struct compute_3d_tile_2d_with_uarch_context context = { - .task = task, - .argument = argument, - .tile_range_j = fxdiv_init_size_t(tile_range_j), - .tile_range_k = fxdiv_init_size_t(tile_range_k), - .range_j = range_j, - .range_k = range_k, - .tile_j = tile_j, - .tile_k = tile_k - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d_with_uarch, ¶ms, sizeof(params), - (void*) compute_3d_tile_2d_with_uarch, &context, range_i * tile_range_j * tile_range_k, flags); - } -} - -struct compute_4d_tile_2d_context { - pthreadpool_task_4d_tile_2d_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_kl; - struct fxdiv_divisor_size_t range_j; - struct fxdiv_divisor_size_t tile_range_l; - size_t range_k; - size_t range_l; - size_t tile_k; - size_t tile_l; -}; - -static void compute_4d_tile_2d(const struct compute_4d_tile_2d_context* context, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_kl = context->tile_range_kl; - const struct fxdiv_result_size_t tile_index_ij_kl = fxdiv_divide_size_t(linear_index, tile_range_kl); - const struct fxdiv_divisor_size_t range_j = context->range_j; - const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_kl.quotient, range_j); - const struct fxdiv_divisor_size_t tile_range_l = context->tile_range_l; - const struct fxdiv_result_size_t tile_index_k_l = fxdiv_divide_size_t(tile_index_ij_kl.remainder, tile_range_l); - const size_t max_tile_k = context->tile_k; - const size_t max_tile_l = context->tile_l; - const size_t index_i = tile_index_i_j.quotient; - const size_t index_j = tile_index_i_j.remainder; - const size_t index_k = tile_index_k_l.quotient * max_tile_k; - const size_t index_l = tile_index_k_l.remainder * max_tile_l; - const size_t tile_k = min(max_tile_k, context->range_k - index_k); - const size_t tile_l = min(max_tile_l, context->range_l - index_l); - context->task(context->argument, index_i, index_j, index_k, index_l, tile_k, tile_l); -} - -void pthreadpool_parallelize_4d_tile_2d( - pthreadpool_t threadpool, - pthreadpool_task_4d_tile_2d_t task, - void* argument, - size_t range_i, - size_t range_j, - size_t range_k, - size_t range_l, - size_t tile_k, - size_t tile_l, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || ((range_i | range_j) <= 1 && range_k <= tile_k && range_l <= tile_l)) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j++) { - for (size_t k = 0; k < range_k; k += tile_k) { - for (size_t l = 0; l < range_l; l += tile_l) { - task(argument, i, j, k, l, - min(range_k - k, tile_k), min(range_l - l, tile_l)); - } - } - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_k = divide_round_up(range_k, tile_k); - const size_t tile_range_l = divide_round_up(range_l, tile_l); - struct compute_4d_tile_2d_context context = { - .task = task, - .argument = argument, - .tile_range_kl = fxdiv_init_size_t(tile_range_k * tile_range_l), - .range_j = fxdiv_init_size_t(range_j), - .tile_range_l = fxdiv_init_size_t(tile_range_l), - .range_k = range_k, - .range_l = range_l, - .tile_k = tile_k, - .tile_l = tile_l - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_4d_tile_2d, &context, range_i * range_j * tile_range_k * tile_range_l, flags); - } -} - -struct compute_4d_tile_2d_with_uarch_context { - pthreadpool_task_4d_tile_2d_with_id_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_kl; - struct fxdiv_divisor_size_t range_j; - struct fxdiv_divisor_size_t tile_range_l; - size_t range_k; - size_t range_l; - size_t tile_k; - size_t tile_l; -}; - -static void compute_4d_tile_2d_with_uarch(const struct compute_4d_tile_2d_with_uarch_context* context, uint32_t uarch_index, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_kl = context->tile_range_kl; - const struct fxdiv_result_size_t tile_index_ij_kl = fxdiv_divide_size_t(linear_index, tile_range_kl); - const struct fxdiv_divisor_size_t range_j = context->range_j; - const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_kl.quotient, range_j); - const struct fxdiv_divisor_size_t tile_range_l = context->tile_range_l; - const struct fxdiv_result_size_t tile_index_k_l = fxdiv_divide_size_t(tile_index_ij_kl.remainder, tile_range_l); - const size_t max_tile_k = context->tile_k; - const size_t max_tile_l = context->tile_l; - const size_t index_i = tile_index_i_j.quotient; - const size_t index_j = tile_index_i_j.remainder; - const size_t index_k = tile_index_k_l.quotient * max_tile_k; - const size_t index_l = tile_index_k_l.remainder * max_tile_l; - const size_t tile_k = min(max_tile_k, context->range_k - index_k); - const size_t tile_l = min(max_tile_l, context->range_l - index_l); - context->task(context->argument, uarch_index, index_i, index_j, index_k, index_l, tile_k, tile_l); -} - -void pthreadpool_parallelize_4d_tile_2d_with_uarch( - pthreadpool_t threadpool, - pthreadpool_task_4d_tile_2d_with_id_t task, - void* argument, - uint32_t default_uarch_index, - uint32_t max_uarch_index, - size_t range_i, - size_t range_j, - size_t range_k, - size_t range_l, - size_t tile_k, - size_t tile_l, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || ((range_i | range_j) <= 1 && range_k <= tile_k && range_l <= tile_l)) { - /* No thread pool used: execute task sequentially on the calling thread */ - - uint32_t uarch_index = default_uarch_index; - #if PTHREADPOOL_USE_CPUINFO - if (threadpool && threadpool->cpuinfo_is_initialized) { - uarch_index = cpuinfo_get_current_uarch_index(); - if (uarch_index > max_uarch_index) { - uarch_index = default_uarch_index; - } - } - #endif - - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j++) { - for (size_t k = 0; k < range_k; k += tile_k) { - for (size_t l = 0; l < range_l; l += tile_l) { - task(argument, uarch_index, i, j, k, l, - min(range_k - k, tile_k), min(range_l - l, tile_l)); - } - } - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_k = divide_round_up(range_k, tile_k); - const size_t tile_range_l = divide_round_up(range_l, tile_l); - const struct pthreadpool_1d_with_uarch_params params = { - .default_uarch_index = default_uarch_index, - .max_uarch_index = max_uarch_index, - }; - struct compute_4d_tile_2d_with_uarch_context context = { - .task = task, - .argument = argument, - .tile_range_kl = fxdiv_init_size_t(tile_range_k * tile_range_l), - .range_j = fxdiv_init_size_t(range_j), - .tile_range_l = fxdiv_init_size_t(tile_range_l), - .range_k = range_k, - .range_l = range_l, - .tile_k = tile_k, - .tile_l = tile_l - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d_with_uarch, ¶ms, sizeof(params), - (void*) compute_4d_tile_2d_with_uarch, &context, range_i * range_j * tile_range_k * tile_range_l, flags); - } -} - -struct compute_5d_tile_2d_context { - pthreadpool_task_5d_tile_2d_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_lm; - struct fxdiv_divisor_size_t range_k; - struct fxdiv_divisor_size_t tile_range_m; - struct fxdiv_divisor_size_t range_j; - size_t range_l; - size_t range_m; - size_t tile_l; - size_t tile_m; -}; - -static void compute_5d_tile_2d(const struct compute_5d_tile_2d_context* context, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_lm = context->tile_range_lm; - const struct fxdiv_result_size_t tile_index_ijk_lm = fxdiv_divide_size_t(linear_index, tile_range_lm); - const struct fxdiv_divisor_size_t range_k = context->range_k; - const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lm.quotient, range_k); - const struct fxdiv_divisor_size_t tile_range_m = context->tile_range_m; - const struct fxdiv_result_size_t tile_index_l_m = fxdiv_divide_size_t(tile_index_ijk_lm.remainder, tile_range_m); - const struct fxdiv_divisor_size_t range_j = context->range_j; - const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, range_j); - - const size_t max_tile_l = context->tile_l; - const size_t max_tile_m = context->tile_m; - const size_t index_i = tile_index_i_j.quotient; - const size_t index_j = tile_index_i_j.remainder; - const size_t index_k = tile_index_ij_k.remainder; - const size_t index_l = tile_index_l_m.quotient * max_tile_l; - const size_t index_m = tile_index_l_m.remainder * max_tile_m; - const size_t tile_l = min(max_tile_l, context->range_l - index_l); - const size_t tile_m = min(max_tile_m, context->range_m - index_m); - context->task(context->argument, index_i, index_j, index_k, index_l, index_m, tile_l, tile_m); -} - -void pthreadpool_parallelize_5d_tile_2d( - pthreadpool_t threadpool, - pthreadpool_task_5d_tile_2d_t task, - void* argument, - size_t range_i, - size_t range_j, - size_t range_k, - size_t range_l, - size_t range_m, - size_t tile_l, - size_t tile_m, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || ((range_i | range_j | range_k) <= 1 && range_l <= tile_l && range_m <= tile_m)) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j++) { - for (size_t k = 0; k < range_k; k++) { - for (size_t l = 0; l < range_l; l += tile_l) { - for (size_t m = 0; m < range_m; m += tile_m) { - task(argument, i, j, k, l, m, - min(range_l - l, tile_l), min(range_m - m, tile_m)); - } - } - } - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_l = divide_round_up(range_l, tile_l); - const size_t tile_range_m = divide_round_up(range_m, tile_m); - struct compute_5d_tile_2d_context context = { - .task = task, - .argument = argument, - .tile_range_lm = fxdiv_init_size_t(tile_range_l * tile_range_m), - .range_k = fxdiv_init_size_t(range_k), - .tile_range_m = fxdiv_init_size_t(tile_range_m), - .range_j = fxdiv_init_size_t(range_j), - .range_l = range_l, - .range_m = range_m, - .tile_l = tile_l, - .tile_m = tile_m, - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_5d_tile_2d, &context, range_i * range_j * range_k * tile_range_l * tile_range_m, flags); - } -} - -struct compute_6d_tile_2d_context { - pthreadpool_task_6d_tile_2d_t task; - void* argument; - struct fxdiv_divisor_size_t tile_range_lmn; - struct fxdiv_divisor_size_t range_k; - struct fxdiv_divisor_size_t tile_range_n; - struct fxdiv_divisor_size_t range_j; - struct fxdiv_divisor_size_t tile_range_m; - size_t range_m; - size_t range_n; - size_t tile_m; - size_t tile_n; -}; - -static void compute_6d_tile_2d(const struct compute_6d_tile_2d_context* context, size_t linear_index) { - const struct fxdiv_divisor_size_t tile_range_lmn = context->tile_range_lmn; - const struct fxdiv_result_size_t tile_index_ijk_lmn = fxdiv_divide_size_t(linear_index, tile_range_lmn); - const struct fxdiv_divisor_size_t range_k = context->range_k; - const struct fxdiv_result_size_t tile_index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lmn.quotient, range_k); - const struct fxdiv_divisor_size_t tile_range_n = context->tile_range_n; - const struct fxdiv_result_size_t tile_index_lm_n = fxdiv_divide_size_t(tile_index_ijk_lmn.remainder, tile_range_n); - const struct fxdiv_divisor_size_t range_j = context->range_j; - const struct fxdiv_result_size_t tile_index_i_j = fxdiv_divide_size_t(tile_index_ij_k.quotient, range_j); - const struct fxdiv_divisor_size_t tile_range_m = context->tile_range_m; - const struct fxdiv_result_size_t tile_index_l_m = fxdiv_divide_size_t(tile_index_lm_n.quotient, tile_range_m); - - const size_t max_tile_m = context->tile_m; - const size_t max_tile_n = context->tile_n; - const size_t index_i = tile_index_i_j.quotient; - const size_t index_j = tile_index_i_j.remainder; - const size_t index_k = tile_index_ij_k.remainder; - const size_t index_l = tile_index_l_m.quotient; - const size_t index_m = tile_index_l_m.remainder * max_tile_m; - const size_t index_n = tile_index_lm_n.remainder * max_tile_n; - const size_t tile_m = min(max_tile_m, context->range_m - index_m); - const size_t tile_n = min(max_tile_n, context->range_n - index_n); - context->task(context->argument, index_i, index_j, index_k, index_l, index_m, index_n, tile_m, tile_n); -} - -void pthreadpool_parallelize_6d_tile_2d( - pthreadpool_t threadpool, - pthreadpool_task_6d_tile_2d_t task, - void* argument, - size_t range_i, - size_t range_j, - size_t range_k, - size_t range_l, - size_t range_m, - size_t range_n, - size_t tile_m, - size_t tile_n, - uint32_t flags) -{ - if (threadpool == NULL || threadpool->threads_count <= 1 || ((range_i | range_j | range_k | range_l) <= 1 && range_m <= tile_m && range_n <= tile_n)) { - /* No thread pool used: execute task sequentially on the calling thread */ - struct fpu_state saved_fpu_state = { 0 }; - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - saved_fpu_state = get_fpu_state(); - disable_fpu_denormals(); - } - for (size_t i = 0; i < range_i; i++) { - for (size_t j = 0; j < range_j; j++) { - for (size_t k = 0; k < range_k; k++) { - for (size_t l = 0; l < range_l; l++) { - for (size_t m = 0; m < range_m; m += tile_m) { - for (size_t n = 0; n < range_n; n += tile_n) { - task(argument, i, j, k, l, m, n, - min(range_m - m, tile_m), min(range_n - n, tile_n)); - } - } - } - } - } - } - if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { - set_fpu_state(saved_fpu_state); - } - } else { - /* Execute in parallel on the thread pool using linearized index */ - const size_t tile_range_m = divide_round_up(range_m, tile_m); - const size_t tile_range_n = divide_round_up(range_n, tile_n); - struct compute_6d_tile_2d_context context = { - .task = task, - .argument = argument, - .tile_range_lmn = fxdiv_init_size_t(range_l * tile_range_m * tile_range_n), - .range_k = fxdiv_init_size_t(range_k), - .tile_range_n = fxdiv_init_size_t(tile_range_n), - .range_j = fxdiv_init_size_t(range_j), - .tile_range_m = fxdiv_init_size_t(tile_range_m), - .range_m = range_m, - .range_n = range_n, - .tile_m = tile_m, - .tile_n = tile_n, - }; - pthreadpool_parallelize( - threadpool, &thread_parallelize_1d, NULL, 0, - (void*) compute_6d_tile_2d, &context, range_i * range_j * range_k * range_l * tile_range_m * tile_range_n, flags); - } -} - -void pthreadpool_destroy(struct pthreadpool* threadpool) { - if (threadpool != NULL) { - const size_t threads_count = threadpool->threads_count; - if (threads_count > 1) { - #if PTHREADPOOL_USE_FUTEX - pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); - pthreadpool_store_relaxed_uint32_t(&threadpool->has_active_threads, 1); - - /* - * Store the command with release semantics to guarantee that if a worker thread observes - * the new command value, it also observes the updated active_threads/has_active_threads values. - */ - pthreadpool_store_release_uint32_t(&threadpool->command, threadpool_command_shutdown); - - /* Wake up worker threads */ - futex_wake_all(&threadpool->command); - #else - /* Lock the command variable to ensure that threads don't shutdown until both command and active_threads are updated */ - pthread_mutex_lock(&threadpool->command_mutex); - - pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); - - /* - * Store the command with release semantics to guarantee that if a worker thread observes - * the new command value, it also observes the updated active_threads value. - * - * Note: the release fence inside pthread_mutex_unlock is insufficient, - * because the workers might be waiting in a spin-loop rather than the conditional variable. - */ - pthreadpool_store_release_uint32_t(&threadpool->command, threadpool_command_shutdown); - - /* Wake up worker threads */ - pthread_cond_broadcast(&threadpool->command_condvar); - - /* Commit the state changes and let workers start processing */ - pthread_mutex_unlock(&threadpool->command_mutex); - #endif - - /* Wait until all threads return */ - for (size_t thread = 1; thread < threads_count; thread++) { - pthread_join(threadpool->threads[thread].thread_object, NULL); - } - - /* Release resources */ - pthread_mutex_destroy(&threadpool->execution_mutex); - #if !PTHREADPOOL_USE_FUTEX - pthread_mutex_destroy(&threadpool->completion_mutex); - pthread_cond_destroy(&threadpool->completion_condvar); - pthread_mutex_destroy(&threadpool->command_mutex); - pthread_cond_destroy(&threadpool->command_condvar); - #endif - } - #if PTHREADPOOL_USE_CPUINFO - if (threadpool->cpuinfo_is_initialized) { - cpuinfo_deinitialize(); - } - #endif - #ifdef _WIN32 - _aligned_free(threadpool); - #else - free(threadpool); - #endif - } -} diff --git a/src/threadpool-utils.h b/src/threadpool-utils.h index 65c7fb0..24fee43 100644 --- a/src/threadpool-utils.h +++ b/src/threadpool-utils.h @@ -1,13 +1,24 @@ #pragma once #include <stdint.h> +#include <stddef.h> -#if defined(__SSE__) || defined(__x86_64__) -#include <xmmintrin.h> +/* SSE-specific headers */ +#if defined(__SSE__) || defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) || (defined(_M_IX86_FP) && _M_IX86_FP >= 1) + #include <xmmintrin.h> #endif +/* MSVC-specific headers */ +#if defined(_MSC_VER) && _MSC_VER >= 1920 + #include <intrin.h> + #if defined(_M_IX86) || defined(_M_X64) || defined(_M_AMD64) + #include <immintrin.h> + #endif +#endif + + struct fpu_state { -#if defined(__SSE__) || defined(__x86_64__) +#if defined(__SSE__) || defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) || (defined(_M_IX86_FP) && _M_IX86_FP >= 1) uint32_t mxcsr; #elif defined(__arm__) && defined(__ARM_FP) && (__ARM_FP != 0) uint32_t fpscr; @@ -20,7 +31,7 @@ struct fpu_state { static inline struct fpu_state get_fpu_state() { struct fpu_state state = { 0 }; -#if defined(__SSE__) || defined(__x86_64__) +#if defined(__SSE__) || defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) || (defined(_M_IX86_FP) && _M_IX86_FP >= 1) state.mxcsr = (uint32_t) _mm_getcsr(); #elif defined(__arm__) && defined(__ARM_FP) && (__ARM_FP != 0) __asm__ __volatile__("VMRS %[fpscr], fpscr" : [fpscr] "=r" (state.fpscr)); @@ -31,7 +42,7 @@ static inline struct fpu_state get_fpu_state() { } static inline void set_fpu_state(const struct fpu_state state) { -#if defined(__SSE__) || defined(__x86_64__) +#if defined(__SSE__) || defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) || (defined(_M_IX86_FP) && _M_IX86_FP >= 1) _mm_setcsr((unsigned int) state.mxcsr); #elif defined(__arm__) && defined(__ARM_FP) && (__ARM_FP != 0) __asm__ __volatile__("VMSR fpscr, %[fpscr]" : : [fpscr] "r" (state.fpscr)); @@ -41,7 +52,7 @@ static inline void set_fpu_state(const struct fpu_state state) { } static inline void disable_fpu_denormals() { -#if defined(__SSE__) || defined(__x86_64__) +#if defined(__SSE__) || defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) || (defined(_M_IX86_FP) && _M_IX86_FP >= 1) _mm_setcsr(_mm_getcsr() | 0x8040); #elif defined(__arm__) && defined(__ARM_FP) && (__ARM_FP != 0) uint32_t fpscr; @@ -60,3 +71,29 @@ static inline void disable_fpu_denormals() { : [fpcr] "=r" (fpcr)); #endif } + +static inline size_t modulo_decrement(size_t i, size_t n) { + /* Wrap modulo n, if needed */ + if (i == 0) { + i = n; + } + /* Decrement input variable */ + return i - 1; +} + +static inline size_t divide_round_up(size_t dividend, size_t divisor) { + if (dividend % divisor == 0) { + return dividend / divisor; + } else { + return dividend / divisor + 1; + } +} + +/* Windows headers define min and max macros; undefine it here */ +#ifdef min + #undef min +#endif + +static inline size_t min(size_t a, size_t b) { + return a < b ? a : b; +} diff --git a/src/windows.c b/src/windows.c new file mode 100644 index 0000000..19e534f --- /dev/null +++ b/src/windows.c @@ -0,0 +1,366 @@ +/* Standard C headers */ +#include <assert.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +/* Configuration header */ +#include "threadpool-common.h" + +/* Windows headers */ +#include <windows.h> + +/* Public library header */ +#include <pthreadpool.h> + +/* Internal library headers */ +#include "threadpool-atomics.h" +#include "threadpool-object.h" +#include "threadpool-utils.h" + + +static void checkin_worker_thread(struct pthreadpool* threadpool, uint32_t event_index) { + if (pthreadpool_decrement_fetch_release_size_t(&threadpool->active_threads) == 0) { + SetEvent(threadpool->completion_event[event_index]); + } +} + +static void wait_worker_threads(struct pthreadpool* threadpool, uint32_t event_index) { + /* Initial check */ + size_t active_threads = pthreadpool_load_acquire_size_t(&threadpool->active_threads); + if (active_threads == 0) { + return; + } + + /* Spin-wait */ + for (uint32_t i = PTHREADPOOL_SPIN_WAIT_ITERATIONS; i != 0; i--) { + /* This fence serves as a sleep instruction */ + pthreadpool_fence_acquire(); + + active_threads = pthreadpool_load_acquire_size_t(&threadpool->active_threads); + if (active_threads == 0) { + return; + } + } + + /* Fall-back to event wait */ + const DWORD wait_status = WaitForSingleObject(threadpool->completion_event[event_index], INFINITE); + assert(wait_status == WAIT_OBJECT_0); + assert(pthreadpool_load_relaxed_size_t(&threadpool->active_threads) == 0); +} + +static uint32_t wait_for_new_command( + struct pthreadpool* threadpool, + uint32_t last_command, + uint32_t last_flags) +{ + uint32_t command = pthreadpool_load_acquire_uint32_t(&threadpool->command); + if (command != last_command) { + return command; + } + + if ((last_flags & PTHREADPOOL_FLAG_YIELD_WORKERS) == 0) { + /* Spin-wait loop */ + for (uint32_t i = PTHREADPOOL_SPIN_WAIT_ITERATIONS; i != 0; i--) { + /* This fence serves as a sleep instruction */ + pthreadpool_fence_acquire(); + + command = pthreadpool_load_acquire_uint32_t(&threadpool->command); + if (command != last_command) { + return command; + } + } + } + + /* Spin-wait disabled or timed out, fall back to event wait */ + const uint32_t event_index = (last_command >> 31); + const DWORD wait_status = WaitForSingleObject(threadpool->command_event[event_index], INFINITE); + assert(wait_status == WAIT_OBJECT_0); + + command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); + assert(command != last_command); + return command; +} + +static DWORD WINAPI thread_main(LPVOID arg) { + struct thread_info* thread = (struct thread_info*) arg; + struct pthreadpool* threadpool = thread->threadpool; + uint32_t last_command = threadpool_command_init; + struct fpu_state saved_fpu_state = { 0 }; + uint32_t flags = 0; + + /* Check in */ + checkin_worker_thread(threadpool, 0); + + /* Monitor new commands and act accordingly */ + for (;;) { + uint32_t command = wait_for_new_command(threadpool, last_command, flags); + pthreadpool_fence_acquire(); + + flags = pthreadpool_load_relaxed_uint32_t(&threadpool->flags); + + /* Process command */ + switch (command & THREADPOOL_COMMAND_MASK) { + case threadpool_command_parallelize: + { + const thread_function_t thread_function = + (thread_function_t) pthreadpool_load_relaxed_void_p(&threadpool->thread_function); + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + + thread_function(threadpool, thread); + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + break; + } + case threadpool_command_shutdown: + /* Exit immediately: the master thread is waiting on pthread_join */ + return 0; + case threadpool_command_init: + /* To inhibit compiler warning */ + break; + } + /* Notify the master thread that we finished processing */ + const uint32_t event_index = command >> 31; + checkin_worker_thread(threadpool, event_index); + /* Update last command */ + last_command = command; + }; + return 0; +} + +struct pthreadpool* pthreadpool_create(size_t threads_count) { + if (threads_count == 0) { + SYSTEM_INFO system_info; + ZeroMemory(&system_info, sizeof(system_info)); + GetSystemInfo(&system_info); + threads_count = (size_t) system_info.dwNumberOfProcessors; + } + + struct pthreadpool* threadpool = pthreadpool_allocate(threads_count); + if (threadpool == NULL) { + return NULL; + } + threadpool->threads_count = fxdiv_init_size_t(threads_count); + for (size_t tid = 0; tid < threads_count; tid++) { + threadpool->threads[tid].thread_number = tid; + threadpool->threads[tid].threadpool = threadpool; + } + + /* Thread pool with a single thread computes everything on the caller thread. */ + if (threads_count > 1) { + threadpool->execution_mutex = CreateMutexW( + NULL /* mutex attributes */, + FALSE /* initially owned */, + NULL /* name */); + for (size_t i = 0; i < 2; i++) { + threadpool->completion_event[i] = CreateEventW( + NULL /* event attributes */, + TRUE /* manual-reset event: yes */, + FALSE /* initial state: nonsignaled */, + NULL /* name */); + threadpool->command_event[i] = CreateEventW( + NULL /* event attributes */, + TRUE /* manual-reset event: yes */, + FALSE /* initial state: nonsignaled */, + NULL /* name */); + } + + pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); + + /* Caller thread serves as worker #0. Thus, we create system threads starting with worker #1. */ + for (size_t tid = 1; tid < threads_count; tid++) { + threadpool->threads[tid].thread_handle = CreateThread( + NULL /* thread attributes */, + 0 /* stack size: default */, + &thread_main, + &threadpool->threads[tid], + 0 /* creation flags */, + NULL /* thread id */); + } + + /* Wait until all threads initialize */ + wait_worker_threads(threadpool, 0); + } + return threadpool; +} + +PTHREADPOOL_INTERNAL void pthreadpool_parallelize( + struct pthreadpool* threadpool, + thread_function_t thread_function, + const void* params, + size_t params_size, + void* task, + void* context, + size_t linear_range, + uint32_t flags) +{ + assert(threadpool != NULL); + assert(thread_function != NULL); + assert(task != NULL); + assert(linear_range > 1); + + /* Protect the global threadpool structures */ + const DWORD wait_status = WaitForSingleObject(threadpool->execution_mutex, INFINITE); + assert(wait_status == WAIT_OBJECT_0); + + /* Setup global arguments */ + pthreadpool_store_relaxed_void_p(&threadpool->thread_function, (void*) thread_function); + pthreadpool_store_relaxed_void_p(&threadpool->task, task); + pthreadpool_store_relaxed_void_p(&threadpool->argument, context); + pthreadpool_store_relaxed_uint32_t(&threadpool->flags, flags); + + const struct fxdiv_divisor_size_t threads_count = threadpool->threads_count; + pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count.value - 1 /* caller thread */); + + if (params_size != 0) { + CopyMemory(&threadpool->params, params, params_size); + pthreadpool_fence_release(); + } + + /* Spread the work between threads */ + const struct fxdiv_result_size_t range_params = fxdiv_divide_size_t(linear_range, threads_count); + size_t range_start = 0; + for (size_t tid = 0; tid < threads_count.value; tid++) { + struct thread_info* thread = &threadpool->threads[tid]; + const size_t range_length = range_params.quotient + (size_t) (tid < range_params.remainder); + const size_t range_end = range_start + range_length; + pthreadpool_store_relaxed_size_t(&thread->range_start, range_start); + pthreadpool_store_relaxed_size_t(&thread->range_end, range_end); + pthreadpool_store_relaxed_size_t(&thread->range_length, range_length); + + /* The next subrange starts where the previous ended */ + range_start = range_end; + } + + /* + * Update the threadpool command. + * Imporantly, do it after initializing command parameters (range, task, argument, flags) + * ~(threadpool->command | THREADPOOL_COMMAND_MASK) flips the bits not in command mask + * to ensure the unmasked command is different then the last command, because worker threads + * monitor for change in the unmasked command. + */ + const uint32_t old_command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); + const uint32_t new_command = ~(old_command | THREADPOOL_COMMAND_MASK) | threadpool_command_parallelize; + + /* + * Reset the command event for the next command. + * It is important to reset the event before writing out the new command, because as soon as the worker threads + * observe the new command, they may process it and switch to waiting on the next command event. + * + * Note: the event is different from the command event signalled in this update. + */ + const uint32_t event_index = (old_command >> 31); + BOOL reset_event_status = ResetEvent(threadpool->command_event[event_index ^ 1]); + assert(reset_event_status != FALSE); + + /* + * Store the command with release semantics to guarantee that if a worker thread observes + * the new command value, it also observes the updated command parameters. + * + * Note: release semantics is necessary, because the workers might be waiting in a spin-loop + * rather than on the event object. + */ + pthreadpool_store_release_uint32_t(&threadpool->command, new_command); + + /* + * Signal the event to wake up the threads. + * Event in use must be switched after every submitted command to avoid race conditions. + * Choose the event based on the high bit of the command, which is flipped on every update. + */ + const BOOL set_event_status = SetEvent(threadpool->command_event[event_index]); + assert(set_event_status != FALSE); + + /* Save and modify FPU denormals control, if needed */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + + /* Do computations as worker #0 */ + thread_function(threadpool, &threadpool->threads[0]); + + /* Restore FPU denormals control, if needed */ + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + + /* + * Wait until the threads finish computation + * Use the complementary event because it corresponds to the new command. + */ + wait_worker_threads(threadpool, event_index ^ 1); + + /* + * Reset the completion event for the next command. + * Note: the event is different from the one used for waiting in this update. + */ + reset_event_status = ResetEvent(threadpool->completion_event[event_index]); + assert(reset_event_status != FALSE); + + /* Make changes by other threads visible to this thread */ + pthreadpool_fence_acquire(); + + /* Unprotect the global threadpool structures */ + const BOOL release_mutex_status = ReleaseMutex(threadpool->execution_mutex); + assert(release_mutex_status != FALSE); +} + +void pthreadpool_destroy(struct pthreadpool* threadpool) { + if (threadpool != NULL) { + const size_t threads_count = threadpool->threads_count.value; + if (threads_count > 1) { + pthreadpool_store_relaxed_size_t(&threadpool->active_threads, threads_count - 1 /* caller thread */); + + /* + * Store the command with release semantics to guarantee that if a worker thread observes + * the new command value, it also observes the updated active_threads values. + */ + const uint32_t old_command = pthreadpool_load_relaxed_uint32_t(&threadpool->command); + pthreadpool_store_release_uint32_t(&threadpool->command, threadpool_command_shutdown); + + /* + * Signal the event to wake up the threads. + * Event in use must be switched after every submitted command to avoid race conditions. + * Choose the event based on the high bit of the command, which is flipped on every update. + */ + const uint32_t event_index = (old_command >> 31); + const BOOL set_event_status = SetEvent(threadpool->command_event[event_index]); + assert(set_event_status != FALSE); + + /* Wait until all threads return */ + for (size_t tid = 1; tid < threads_count; tid++) { + const HANDLE thread_handle = threadpool->threads[tid].thread_handle; + if (thread_handle != NULL) { + const DWORD wait_status = WaitForSingleObject(thread_handle, INFINITE); + assert(wait_status == WAIT_OBJECT_0); + + const BOOL close_status = CloseHandle(thread_handle); + assert(close_status != FALSE); + } + } + + /* Release resources */ + if (threadpool->execution_mutex != NULL) { + const BOOL close_status = CloseHandle(threadpool->execution_mutex); + assert(close_status != FALSE); + } + for (size_t i = 0; i < 2; i++) { + if (threadpool->command_event[i] != NULL) { + const BOOL close_status = CloseHandle(threadpool->command_event[i]); + assert(close_status != FALSE); + } + if (threadpool->completion_event[i] != NULL) { + const BOOL close_status = CloseHandle(threadpool->completion_event[i]); + assert(close_status != FALSE); + } + } + } + pthreadpool_deallocate(threadpool); + } +} |