Use `partialsort!` on color OrderedDither

[adrhill]

Suggested here, this got lost in PR #53.

[codecov[bot]]

Codecov Report

Merging #62 (28923e3) into master (bb51f94) will not change coverage. The diff coverage is 100.00%.

@@           Coverage Diff           @@
##           master      #62   +/-   ##
=======================================
  Coverage   96.81%   96.81%           
=======================================
  Files          14       14           
  Lines         251      251           
=======================================
  Hits          243      243           
  Misses          8        8           

Impacted Files	Coverage Δ
src/ordered.jl	98.30% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update bb51f94...28923e3. Read the comment docs.

[github-actions[bot]]

Benchmark result

# Judge result # Benchmark Report for */home/runner/work/DitherPunk.jl/DitherPunk.jl* ## Job Properties * Time of benchmarks: - Target: 11 Dec 2021 - 16:29 - Baseline: 11 Dec 2021 - 16:31 * Package commits: - Target: f2fa12 - Baseline: bb51f9 * Julia commits: - Target: 3bf9d1 - Baseline: 3bf9d1 * Julia command flags: - Target: None - Baseline: None * Environment variables: - Target: None - Baseline: None ## Results A ratio greater than `1.0` denotes a possible regression (marked with :x:), while a ratio less than `1.0` denotes a possible improvement (marked with :white_check_mark:). Only significant results - results that indicate possible regressions or improvements - are shown below (thus, an empty table means that all benchmark results remained invariant between builds). | ID | time ratio | memory ratio | |--------------------------------------------------|------------------------------|------------------------------| | `["closest color", "binary inplace"]` | 1.26 (5%) :x: | 1.00 (1%) | | `["closest color", "binary new"]` | 1.31 (5%) :x: | 1.00 (1%) | | `["error diffusion", "binary inplace"]` | 0.80 (5%) :white_check_mark: | 1.00 (1%) | | `["error diffusion", "binary new"]` | 0.81 (5%) :white_check_mark: | 1.00 (1%) | | `["error diffusion", "color inplace"]` | 0.99 (5%) | 1.17 (1%) :x: | | `["error diffusion", "per-channel inplace"]` | 0.95 (5%) :white_check_mark: | 1.00 (1%) | | `["error diffusion", "per-channel new"]` | 0.95 (5%) :white_check_mark: | 1.00 (1%) | | `["ordered dithering", "color inplace"]` | 0.88 (5%) :white_check_mark: | 0.92 (1%) :white_check_mark: | | `["ordered dithering", "color new"]` | 0.93 (5%) :white_check_mark: | 0.93 (1%) :white_check_mark: | | `["threshold dithering", "binary inplace"]` | 1.08 (5%) :x: | 1.00 (1%) | | `["threshold dithering", "binary new"]` | 1.07 (5%) :x: | 1.00 (1%) | ## Benchmark Group List Here's a list of all the benchmark groups executed by this job: - `["closest color"]` - `["error diffusion"]` - `["ordered dithering"]` - `["threshold dithering"]` ## Julia versioninfo ### Target ``` Julia Version 1.7.0 Commit 3bf9d17731 (2021-11-30 12:12 UTC) Platform Info: OS: Linux (x86_64-pc-linux-gnu) Ubuntu 20.04.3 LTS uname: Linux 5.11.0-1021-azure #22~20.04.1-Ubuntu SMP Fri Oct 29 01:11:25 UTC 2021 x86_64 x86_64 CPU: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz: speed user nice sys idle irq #1 2593 MHz 864 s 1 s 111 s 4992 s 0 s #2 2593 MHz 3050 s 1 s 199 s 2735 s 0 s Memory: 6.788982391357422 GB (3358.1171875 MB free) Uptime: 601.89 sec Load Avg: 1.0 0.85 0.45 WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-12.0.1 (ORCJIT, skylake-avx512) ``` ### Baseline ``` Julia Version 1.7.0 Commit 3bf9d17731 (2021-11-30 12:12 UTC) Platform Info: OS: Linux (x86_64-pc-linux-gnu) Ubuntu 20.04.3 LTS uname: Linux 5.11.0-1021-azure #22~20.04.1-Ubuntu SMP Fri Oct 29 01:11:25 UTC 2021 x86_64 x86_64 CPU: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz: speed user nice sys idle irq #1 2593 MHz 2112 s 1 s 124 s 5115 s 0 s #2 2593 MHz 3179 s 1 s 205 s 3981 s 0 s Memory: 6.788982391357422 GB (3496.64453125 MB free) Uptime: 740.34 sec Load Avg: 1.06 0.94 0.54 WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-12.0.1 (ORCJIT, skylake-avx512) ``` --- # Target result # Benchmark Report for */home/runner/work/DitherPunk.jl/DitherPunk.jl* ## Job Properties * Time of benchmark: 11 Dec 2021 - 16:29 * Package commit: f2fa12 * Julia commit: 3bf9d1 * Julia command flags: None * Environment variables: None ## Results Below is a table of this job's results, obtained by running the benchmarks. The values listed in the `ID` column have the structure `[parent_group, child_group, ..., key]`, and can be used to index into the BaseBenchmarks suite to retrieve the corresponding benchmarks. The percentages accompanying time and memory values in the below table are noise tolerances. The "true" time/memory value for a given benchmark is expected to fall within this percentage of the reported value. An empty cell means that the value was zero. | ID | time | GC time | memory | allocations | |--------------------------------------------------|----------------:|----------:|----------------:|------------:| | `["closest color", "binary inplace"]` | 7.834 μs (5%) | | 64.11 KiB (1%) | 2 | | `["closest color", "binary new"]` | 6.450 μs (5%) | | 64.11 KiB (1%) | 2 | | `["closest color", "color inplace"]` | 145.409 ms (5%) | | 36.50 MiB (1%) | 2359336 | | `["closest color", "color new"]` | 147.379 ms (5%) | | 36.48 MiB (1%) | 2357848 | | `["closest color", "per-channel inplace"]` | 1.112 ms (5%) | | 192.05 KiB (1%) | 2 | | `["closest color", "per-channel new"]` | 1.096 ms (5%) | | 192.05 KiB (1%) | 2 | | `["error diffusion", "binary inplace"]` | 870.213 μs (5%) | | 320.23 KiB (1%) | 5 | | `["error diffusion", "binary new"]` | 875.312 μs (5%) | | 320.23 KiB (1%) | 5 | | `["error diffusion", "color inplace"]` | 152.983 ms (5%) | | 37.20 MiB (1%) | 2384768 | | `["error diffusion", "color new"]` | 159.055 ms (5%) | | 31.87 MiB (1%) | 2035592 | | `["error diffusion", "per-channel inplace"]` | 4.115 ms (5%) | | 960.42 KiB (1%) | 11 | | `["error diffusion", "per-channel new"]` | 4.121 ms (5%) | | 960.42 KiB (1%) | 11 | | `["ordered dithering", "binary inplace"]` | 115.501 μs (5%) | | 69.42 KiB (1%) | 5 | | `["ordered dithering", "binary new"]` | 110.002 μs (5%) | | 69.42 KiB (1%) | 5 | | `["ordered dithering", "color inplace"]` | 708.521 ms (5%) | 31.315 ms | 247.07 MiB (1%) | 14417965 | | `["ordered dithering", "color new"]` | 854.531 ms (5%) | 49.122 ms | 281.11 MiB (1%) | 16473466 | | `["ordered dithering", "per-channel inplace"]` | 1.231 ms (5%) | | 207.98 KiB (1%) | 11 | | `["ordered dithering", "per-channel new"]` | 1.214 ms (5%) | | 207.98 KiB (1%) | 11 | | `["threshold dithering", "binary inplace"]` | 15.400 μs (5%) | | 128.27 KiB (1%) | 7 | | `["threshold dithering", "binary new"]` | 12.600 μs (5%) | | 128.27 KiB (1%) | 7 | | `["threshold dithering", "per-channel inplace"]` | 1.138 ms (5%) | | 384.38 KiB (1%) | 8 | | `["threshold dithering", "per-channel new"]` | 1.120 ms (5%) | | 384.38 KiB (1%) | 8 | ## Benchmark Group List Here's a list of all the benchmark groups executed by this job: - `["closest color"]` - `["error diffusion"]` - `["ordered dithering"]` - `["threshold dithering"]` ## Julia versioninfo ``` Julia Version 1.7.0 Commit 3bf9d17731 (2021-11-30 12:12 UTC) Platform Info: OS: Linux (x86_64-pc-linux-gnu) Ubuntu 20.04.3 LTS uname: Linux 5.11.0-1021-azure #22~20.04.1-Ubuntu SMP Fri Oct 29 01:11:25 UTC 2021 x86_64 x86_64 CPU: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz: speed user nice sys idle irq #1 2593 MHz 864 s 1 s 111 s 4992 s 0 s #2 2593 MHz 3050 s 1 s 199 s 2735 s 0 s Memory: 6.788982391357422 GB (3358.1171875 MB free) Uptime: 601.89 sec Load Avg: 1.0 0.85 0.45 WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-12.0.1 (ORCJIT, skylake-avx512) ``` --- # Baseline result # Benchmark Report for */home/runner/work/DitherPunk.jl/DitherPunk.jl* ## Job Properties * Time of benchmark: 11 Dec 2021 - 16:31 * Package commit: bb51f9 * Julia commit: 3bf9d1 * Julia command flags: None * Environment variables: None ## Results Below is a table of this job's results, obtained by running the benchmarks. The values listed in the `ID` column have the structure `[parent_group, child_group, ..., key]`, and can be used to index into the BaseBenchmarks suite to retrieve the corresponding benchmarks. The percentages accompanying time and memory values in the below table are noise tolerances. The "true" time/memory value for a given benchmark is expected to fall within this percentage of the reported value. An empty cell means that the value was zero. | ID | time | GC time | memory | allocations | |--------------------------------------------------|----------------:|----------:|----------------:|------------:| | `["closest color", "binary inplace"]` | 6.234 μs (5%) | | 64.11 KiB (1%) | 2 | | `["closest color", "binary new"]` | 4.925 μs (5%) | | 64.11 KiB (1%) | 2 | | `["closest color", "color inplace"]` | 146.731 ms (5%) | | 36.48 MiB (1%) | 2357848 | | `["closest color", "color new"]` | 147.835 ms (5%) | | 36.48 MiB (1%) | 2357848 | | `["closest color", "per-channel inplace"]` | 1.109 ms (5%) | | 192.05 KiB (1%) | 2 | | `["closest color", "per-channel new"]` | 1.094 ms (5%) | | 192.05 KiB (1%) | 2 | | `["error diffusion", "binary inplace"]` | 1.086 ms (5%) | | 320.23 KiB (1%) | 5 | | `["error diffusion", "binary new"]` | 1.082 ms (5%) | | 320.23 KiB (1%) | 5 | | `["error diffusion", "color inplace"]` | 155.183 ms (5%) | | 31.87 MiB (1%) | 2035592 | | `["error diffusion", "color new"]` | 159.187 ms (5%) | | 31.87 MiB (1%) | 2035592 | | `["error diffusion", "per-channel inplace"]` | 4.344 ms (5%) | | 960.42 KiB (1%) | 11 | | `["error diffusion", "per-channel new"]` | 4.340 ms (5%) | | 960.42 KiB (1%) | 11 | | `["ordered dithering", "binary inplace"]` | 113.473 μs (5%) | | 69.42 KiB (1%) | 5 | | `["ordered dithering", "binary new"]` | 109.802 μs (5%) | | 69.42 KiB (1%) | 5 | | `["ordered dithering", "color inplace"]` | 807.959 ms (5%) | 18.796 ms | 268.07 MiB (1%) | 14483501 | | `["ordered dithering", "color new"]` | 916.946 ms (5%) | 18.174 ms | 302.11 MiB (1%) | 16539002 | | `["ordered dithering", "per-channel inplace"]` | 1.232 ms (5%) | | 207.98 KiB (1%) | 11 | | `["ordered dithering", "per-channel new"]` | 1.214 ms (5%) | | 207.98 KiB (1%) | 11 | | `["threshold dithering", "binary inplace"]` | 14.301 μs (5%) | | 128.27 KiB (1%) | 7 | | `["threshold dithering", "binary new"]` | 11.800 μs (5%) | | 128.27 KiB (1%) | 7 | | `["threshold dithering", "per-channel inplace"]` | 1.138 ms (5%) | | 384.38 KiB (1%) | 8 | | `["threshold dithering", "per-channel new"]` | 1.119 ms (5%) | | 384.38 KiB (1%) | 8 | ## Benchmark Group List Here's a list of all the benchmark groups executed by this job: - `["closest color"]` - `["error diffusion"]` - `["ordered dithering"]` - `["threshold dithering"]` ## Julia versioninfo ``` Julia Version 1.7.0 Commit 3bf9d17731 (2021-11-30 12:12 UTC) Platform Info: OS: Linux (x86_64-pc-linux-gnu) Ubuntu 20.04.3 LTS uname: Linux 5.11.0-1021-azure #22~20.04.1-Ubuntu SMP Fri Oct 29 01:11:25 UTC 2021 x86_64 x86_64 CPU: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz: speed user nice sys idle irq #1 2593 MHz 2112 s 1 s 124 s 5115 s 0 s #2 2593 MHz 3179 s 1 s 205 s 3981 s 0 s Memory: 6.788982391357422 GB (3496.64453125 MB free) Uptime: 740.34 sec Load Avg: 1.06 0.94 0.54 WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-12.0.1 (ORCJIT, skylake-avx512) ``` --- # Runtime information | Runtime Info | | |:--|:--| | BLAS #threads | 2 | | `BLAS.vendor()` | `openblas64` | | `Sys.CPU_THREADS` | 2 | `lscpu` output: Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 46 bits physical, 48 bits virtual CPU(s): 2 On-line CPU(s) list: 0,1 Thread(s) per core: 1 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 85 Model name: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz Stepping: 7 CPU MHz: 2593.903 BogoMIPS: 5187.80 Hypervisor vendor: Microsoft Virtualization type: full L1d cache: 64 KiB L1i cache: 64 KiB L2 cache: 2 MiB L3 cache: 35.8 MiB NUMA node0 CPU(s): 0,1 Vulnerability Itlb multihit: KVM: Mitigation: VMX unsupported Vulnerability L1tf: Mitigation; PTE Inversion Vulnerability Mds: Mitigation; Clear CPU buffers; SMT Host state unknown Vulnerability Meltdown: Mitigation; PTI Vulnerability Spec store bypass: Vulnerable Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization Vulnerability Spectre v2: Mitigation; Full generic retpoline, STIBP disabled, RSB filling Vulnerability Srbds: Not affected Vulnerability Tsx async abort: Mitigation; Clear CPU buffers; SMT Host state unknown Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology cpuid pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm 3dnowprefetch invpcid_single pti fsgsbase bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx avx512f avx512dq rdseed adx smap clflushopt avx512cd avx512bw avx512vl xsaveopt xsavec xsaves md_clear | Cpu Property | Value | |:------------------ |:------------------------------------------------------- | | Brand | Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz | | Vendor | :Intel | | Architecture | :Skylake | | Model | Family: 0x06, Model: 0x55, Stepping: 0x07, Type: 0x00 | | Cores | 2 physical cores, 2 logical cores (on executing CPU) | | | No Hyperthreading hardware capability detected | | Clock Frequencies | Not supported by CPU | | Data Cache | Level 1:3 : (32, 1024, 36608) kbytes | | | 64 byte cache line size | | Address Size | 48 bits virtual, 46 bits physical | | SIMD | 512 bit = 64 byte max. SIMD vector size | | Time Stamp Counter | TSC is accessible via `rdtsc` | | | TSC increased at every clock cycle (non-invariant TSC) | | Perf. Monitoring | Performance Monitoring Counters (PMC) are not supported | | Hypervisor | Yes, Microsoft |