## [Line Charts]: Performance Comparison of Sorting Algorithms (WMS, BMS, RB-Sort)
### Overview
The image contains six line charts arranged in a 2x3 grid. They compare the average running time (in milliseconds) of three sorting algorithms—WMS, BMS, and RB-Sort—as a function of the number of buckets (m). The comparison is performed across two data types ("key-only" and "key-value") and three hardware/configurations: Tesla K40c with ECC on, Tesla K40c with ECC off, and GeForce GTX 1080.
### Components/Axes
* **Chart Layout:** Six subplots labeled (a) through (f).
* **X-Axis (All Charts):** "Number of buckets (m)". The scale is logarithmic, with major tick marks at 1, 2, 4, 8, 16, 32, 64, 128, and 256.
* **Y-Axis (All Charts):** "Average running time (ms)". The scale is linear but varies in range per chart.
* **Legend (All Charts):** Located in the top-left corner of each subplot.
* `WMS`: Red line with circle markers.
* `BMS`: Green line with triangle markers.
* `RB-Sort`: Blue line with plus sign markers.
* **Subplot Titles:**
* (a) `key-only: Tesla K40c (ECC on)`
* (b) `key-only: Tesla K40c (ECC off)`
* (c) `key-only: GeForce GTX 1080`
* (d) `key-value: Tesla K40c (ECC on)`
* (e) `key-value: Tesla K40c (ECC off)`
* (f) `key-value: GeForce GTX 1080`
### Detailed Analysis
**Trend Verification & Data Point Extraction (Approximate Values):**
**Top Row: Key-Only Data**
* **Chart (a) K40c (ECC on):**
* **RB-Sort (Blue +):** Starts at ~6 ms (m=1), increases steadily to ~13 ms (m=256). Trend: Consistently highest running time, steep upward slope.
* **BMS (Green △):** Starts at ~4 ms (m=1), remains flat until m=16, then increases sharply to ~13 ms (m=256). Trend: Flat then steep rise, converges with RB-Sort at m=256.
* **WMS (Red ○):** Starts at ~3 ms (m=1), increases gradually to ~4.5 ms (m=32). Data series ends at m=32. Trend: Lowest running time, gentle upward slope.
* **Chart (b) K40c (ECC off):**
* **RB-Sort (Blue +):** Starts at ~5 ms (m=1), increases to ~9 ms (m=256). Trend: Highest running time, moderate upward slope.
* **BMS (Green △):** Starts at ~4 ms (m=1), increases to ~13 ms (m=256). Trend: Steeper increase than RB-Sort, surpasses it at m=128.
* **WMS (Red ○):** Starts at ~2.5 ms (m=1), increases to ~4.5 ms (m=32). Data series ends at m=32. Trend: Lowest running time.
* **Chart (c) GTX 1080:**
* **RB-Sort (Blue +):** Starts at ~4 ms (m=1), increases to ~7 ms (m=256). Trend: Highest running time, moderate upward slope.
* **BMS (Green △):** Starts at ~1.8 ms (m=1), remains flat until m=64, then increases to ~5 ms (m=256). Trend: Flat then sharp rise.
* **WMS (Red ○):** Starts at ~1.8 ms (m=1), increases to ~3 ms (m=32). Data series ends at m=32. Trend: Similar to BMS initially, then lower.
**Bottom Row: Key-Value Data**
* **Chart (d) K40c (ECC on):**
* **RB-Sort (Blue +):** Starts at ~12 ms (m=1), increases steeply to ~25 ms (m=256). Trend: Highest running time, very steep upward slope.
* **BMS (Green △):** Starts at ~3 ms (m=1), increases to ~18 ms (m=256). Trend: Steep increase, remains below RB-Sort.
* **WMS (Red ○):** Starts at ~3 ms (m=1), increases to ~6 ms (m=64). Data series ends at m=64. Trend: Lowest running time.
* **Chart (e) K40c (ECC off):**
* **RB-Sort (Blue +):** Starts at ~11 ms (m=1), increases to ~18 ms (m=256). Trend: Highest running time.
* **BMS (Green △):** Starts at ~4 ms (m=1), increases to ~18 ms (m=256). Trend: Steep increase, converges with RB-Sort at m=256.
* **WMS (Red ○):** Starts at ~3 ms (m=1), increases to ~7 ms (m=64). Data series ends at m=64. Trend: Lowest running time.
* **Chart (f) GTX 1080:**
* **RB-Sort (Blue +):** Starts at ~9 ms (m=1), increases to ~14 ms (m=256). Trend: Highest running time.
* **BMS (Green △):** Starts at ~2.5 ms (m=1), remains flat until m=128, then increases to ~6 ms (m=256). Trend: Very flat until a late, sharp rise.
* **WMS (Red ○):** Starts at ~2.5 ms (m=1), increases to ~4.5 ms (m=64). Data series ends at m=64. Trend: Lowest running time.
### Key Observations
1. **Algorithm Hierarchy:** Across all configurations, RB-Sort consistently has the highest average running time. WMS consistently has the lowest, followed by BMS.
2. **Scalability:** The running time for all algorithms increases with the number of buckets (m). The rate of increase (slope) is generally steepest for RB-Sort and BMS at higher `m` values, especially for key-value data.
3. **Data Type Impact:** Running times are significantly higher for "key-value" data compared to "key-only" data for the same hardware and algorithm (e.g., compare (a) vs (d)).
4. **Hardware Impact:** The GeForce GTX 1080 generally shows lower running times than the Tesla K40c for the same data type and algorithm (e.g., compare (a) vs (c)).
5. **ECC Impact:** Disabling ECC on the Tesla K40c reduces running times for all algorithms (compare (a) vs (b), (d) vs (e)).
6. **WMS Data Limit:** The WMS algorithm's data series terminates earlier (at m=32 or m=64) than BMS and RB-Sort (which go to m=256) in all charts.
### Interpretation
This set of charts provides a performance benchmark for three sorting algorithms under varying conditions. The data suggests that **RB-Sort is the least efficient** of the three in terms of running time, while **WMS is the most efficient**. However, the early termination of the WMS data series might indicate a limitation in its scalability or applicability for a large number of buckets.
The **key-value operation is more computationally expensive** than the key-only operation, as expected. The **impact of hardware is clear**, with the consumer-grade GTX 1080 outperforming the professional-grade K40c in these specific tests. Furthermore, **enabling ECC memory on the K40c introduces a measurable performance overhead**, which is a known trade-off for increased reliability.
The most notable trend is the **divergent scalability** of the algorithms. BMS and RB-Sort show a non-linear, accelerating increase in running time as `m` grows, particularly for key-value data. In contrast, WMS shows a more linear and gentle increase, though its limited data range prevents a full comparison at high `m`. This suggests WMS may have a better algorithmic complexity class for this specific task, but its practical upper limit on `m` needs investigation. The charts effectively demonstrate the performance trade-offs between algorithm choice, data complexity, hardware selection, and system configuration (ECC).