QuantumSavory / QuantumSavory.jl

A full stack simulator of quantum hardware, from the low-level analog physics to high-level network dynamics. Includes discrete event simulator, symbolic representation for quantum object, and works with many backend simulators.
https://quantumsavory.github.io/QuantumSavory.jl/
MIT License
30 stars 11 forks source link

simplify the `query` implementation #121

Closed Krastanov closed 3 months ago

Krastanov commented 3 months ago

This code is drastically simpler than the original implementation, but also much slower:

Kept here as a reference and for potential future work that might be both simpler and faster.

## before any simplification

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  134.635 μs …   6.296 ms  ┊ GC (min … max): 0.00% … 95.01%
 Time  (median):     142.902 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   160.930 μs ± 240.887 μs  ┊ GC (mean ± σ):  8.04% ±  5.30%

    ▂▇██▅▂
  ▃▅███████▇▆▅▅▅▅▅▅▅▄▄▄▃▃▃▃▃▃▃▃▃▃▃▂▂▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂▂▂ ▃
  135 μs           Histogram: frequency by time          205 μs <

 Memory estimate: 214.33 KiB, allocs estimate: 2649.

## after first round of simplification

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  171.124 μs …  10.533 ms  ┊ GC (min … max): 0.00% … 96.97%
 Time  (median):     182.391 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   200.198 μs ± 291.337 μs  ┊ GC (mean ± σ):  6.32% ±  4.33%

    ▁▆███▇▃▂
  ▁▃██████████▇▇▆▅▄▄▄▃▃▃▂▂▂▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▃
  171 μs           Histogram: frequency by time          256 μs <

 Memory estimate: 226.64 KiB, allocs estimate: 2848.

## after second round of simplification

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  331.740 μs …   6.718 ms  ┊ GC (min … max): 0.00% … 91.94%
 Time  (median):     344.995 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   368.845 μs ± 261.286 μs  ┊ GC (mean ± σ):  5.52% ±  7.07%

     ▅██▆▃▂
  ▂▃▇███████▆▆▅▄▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂▂▂▁▁▁▁▁▂▂▁▁▁▁▁▁▂▂▂▁▂ ▃
  332 μs           Histogram: frequency by time          458 μs <

 Memory estimate: 436.03 KiB, allocs estimate: 8666.
Krastanov commented 3 months ago

some more microbenchmarks showing more clearly the order-of-magnitude difference:

using QuantumSavory
using QuantumSavory.ProtocolZoo
using BenchmarkTools

reg = Register(5)
tag!(reg[3], EntanglementCounterpart, 1, 10)
tag!(reg[3], EntanglementCounterpart, 2, 21)
tag!(reg[3], EntanglementCounterpart, 3, 30)
tag!(reg[3], EntanglementCounterpart, 2, 22)
tag!(reg[3], EntanglementCounterpart, 1, 10)
tag!(reg[3], EntanglementCounterpart, 6, 60)
tag!(reg[3], EntanglementCounterpart, 2, 23)
tag!(reg[3], EntanglementCounterpart, 1, 10)

@benchmark query(reg, EntanglementCounterpart, 6, ❓; filo=true)

##
#=

# before

BenchmarkTools.Trial: 10000 samples with 217 evaluations.
 Range (min … max):  349.700 ns …  20.329 μs  ┊ GC (min … max): 0.00% … 97.32%
 Time  (median):     363.272 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   393.885 ns ± 410.384 ns  ┊ GC (mean ± σ):  3.76% ±  3.76%

   ▁▃▇█▇▅▃▁▁▃▃▂▁                                       ▁▂▂▂▂▂▁  ▂
  ████████████████▇▇▆▇▆▅▆▆▆▄▄▅▃▄▃▄▅▇█▆▇█▇▇▄▃▃▁▃▁▃▄▄▃▆▇█████████ █
  350 ns        Histogram: log(frequency) by time        519 ns <

 Memory estimate: 512 bytes, allocs estimate: 8.

# after

BenchmarkTools.Trial: 10000 samples with 7 evaluations.
 Range (min … max):  4.225 μs … 313.888 μs  ┊ GC (min … max): 0.00% … 96.58%
 Time  (median):     4.343 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   4.503 μs ±   5.284 μs  ┊ GC (mean ± σ):  1.98% ±  1.67%

   ▄▇█▇▅▃▂                                                    ▂
  ▆████████▇▆▇▇▇▆▆▅▅▆▄▇█▇▇▅▅▄▅▄▄▅▆▅▅▅▅▅▅▄▅▅▅▄▂▄▅▄▅▅▆▅▃▄▄▄▃▄▄▄ █
  4.23 μs      Histogram: log(frequency) by time       6.1 μs <

 Memory estimate: 3.53 KiB, allocs estimate: 79.
codecov[bot] commented 3 months ago

Codecov Report

Attention: Patch coverage is 88.70968% with 7 lines in your changes missing coverage. Please review.

Project coverage is 73.45%. Comparing base (10e94f0) to head (ddb00ea).

Files Patch % Lines
src/queries.jl 87.93% 7 Missing :warning:
Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #121 +/- ## ========================================== - Coverage 73.62% 73.45% -0.18% ========================================== Files 38 38 Lines 1695 1695 ========================================== - Hits 1248 1245 -3 - Misses 447 450 +3 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.