mapcrafter / mapcrafter/mapcrafter

High thread synchronization overhead

Open
#180 6 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Bug Feature Request Performance
Dominant language
C++
Stars
643
Forks
156
PR merge metrics
No merged PRs in 30d

Description

Noticed that there is fairly high synchronization overhead in your implementation - as the number of threads is increased the overall throughput decreases. Here's a table showing my findings, using mapcrafter-gui 2.1 x64 for Windows. Command-line had similar performance as well. I completely delete the output directory before each run. My system has 32 logical processors and ludicrously-fast I/O.

| Threads | Tiles per second | Notes |
| --- | --- | --- |
| 4 | 67.1 | |
| 8 | 93.1 | |
| 10 | 74.4 | |
| 12 | 59.9 | |
| 16 | 42.6 | |
| 24 | 30.2 | |
| 32 | 20.7 | |
| 64 | 12.1 | 9% CPU usage - 2 threads per core |
| 96 | 10.1 | 8% CPU usage - 3 threads per core |

During these runs I noticed that a single core had significantly higher CPU usage than the rest - and that CPU usage is spent mostly in kernel mode, presumably waiting on a thread synchronization primitive.

I took a quick look at the source code and found that the ThreadManager::mutex is highly contended by the worker threads. I believe performance may be increased by making these changes to the thread manager and work queue classes:
- The thread manager mutex is gone. I don't believe it's necessary as long as there are proper memory barriers.
- Condition variables are always notified when you add something to a queue; they may act as a memory fence, but I'm not 100% sure.
- ConcurrentQueue's mutex can be removed and replaced with similar constructs as well.
- Alternatively: http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-free-queue-for-c++ - but this is a more extensive change.

Fixing this would allow a 7.5GB map to be rendered under 4 minutes on my system, instead of in 16 minutes. I'm not a C++ developer, unfortunately.

Configuration:

```
output_dir = C:\Users\Myself\Documents\git\KMobile\src\main\webapp\map

[world:kreatious]
input_dir = R:\kreatious\2015-05-09-21k
crop_min_x = -5000
crop_min_z = -5000
crop_max_x = 15000
crop_max_z = 15000

[map:map_kreatious]
name = Kreatious
world = kreatious
render_view = topdown
texture_size = 4
tile_width = 4
png_indexed = true
```

The world being rendered is 7.5 GB

I/O speeds, as measured by CrystalDiskMark, with a queue depth of 1, using 32 threads on 16GB of data; to best represent the I/O pattern used by mapcrafter:

> C:\ sequential read/write 17.3/19.3 GB/s
> C:\ random 4K read/write 1.2/1.0 GB/s
> R:\ sequential read/write 18.5/15.6 GB/s
> R:\ random 4k read/write 1.2/1.0 GB/s

A single thread can sequentially read/write 3.6/3.9 GB/s, and randomly read/write 414.7/440.4 MB/s
Sanity check: `time cat /r/kreatious/2015-05-09-21k/region/*.mca > /dev/null` takes 2.343s

System specifications:

> Windows 10 64-bit
> Running http://mapcrafter.org/windows/main/mapcrafter_2.1_win64.zip using mapcrafter-gui
> 2 Xeon E5-2687W processors (32 logical cores)
> 128GB of RAM
> DIsk read/writes are cached in memory

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by locating ThreadManager, the work queue classes, and ConcurrentQueue, then inspect how worker threads synchronize and receive work. Reproduce the thread-scaling benchmark described in the issue and measure contention and throughput. Done means reduced synchronization overhead without incorrect queue behavior, with improved scaling against the reported workload.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.