mnemonikr / symbolic-pcode

Apache License 2.0
0 stars 0 forks source link

Performance improvements to several SymbolicBitVec APIs #135

Closed mnemonikr closed 4 weeks ago

mnemonikr commented 4 weeks ago

This change updated the internals of SymbolicBitVec to use a VecDeque instead of a Vec. This helped improve performance for multiply and divide APIs. Also ported the shift implementations from SymbolicBitBuf, which resulted in marked improvements to the shift left and shift right APIs.

This change also removed some conversions from SymbolicBitVec. Converting directly to a SymbolicBit was not used in practice, so this was removed. This can still be achieved using len() == 1 and msb().

Additionally the Deref implementation into a slice has been removed, since a VecDeque cannot make the same contiguous guarantees. The common APIs used such as len, is_empty, and the Index trait impl have been implemented directly on SymbolicBitVec instead.

Resolves #57 Resolves #95

mnemonikr commented 4 weeks ago

Performance improvements compared to main:

Emulate/Arithmetic/Int(ShiftLeft)
                        time:   [90.350 µs 90.731 µs 91.202 µs]
                        change: [-60.043% -59.768% -59.418%] (p = 0.00 < 0.05)
                        Performance has improved.

Emulate/Arithmetic/Int(ShiftRight(Signed))
                        time:   [86.889 µs 87.203 µs 87.555 µs]
                        change: [-55.663% -55.379% -54.971%] (p = 0.00 < 0.05)
                        Performance has improved.

Emulate/Arithmetic/Int(Multiply)
                        time:   [256.98 µs 257.42 µs 257.97 µs]
                        change: [-22.909% -22.446% -22.030%] (p = 0.00 < 0.05)
                        Performance has improved.

Emulate/Arithmetic/Int(Divide(Unsigned))
                        time:   [1.0931 ms 1.0967 ms 1.1004 ms]
                        change: [-15.115% -14.859% -14.590%] (p = 0.00 < 0.05)
                        Performance has improved.

Emulate/Arithmetic/Int(Divide(Signed))
                        time:   [1.1193 ms 1.1212 ms 1.1230 ms]
                        change: [-15.809% -15.465% -15.143%] (p = 0.00 < 0.05)
                        Performance has improved.

Emulate/Arithmetic/Int(Remainder(Unsigned))
                        time:   [1.1040 ms 1.1061 ms 1.1081 ms]
                        change: [-15.434% -15.044% -14.667%] (p = 0.00 < 0.05)
                        Performance has improved.

Emulate/Arithmetic/Int(Remainder(Signed))
                        time:   [1.1365 ms 1.1403 ms 1.1446 ms]
                        change: [-14.163% -13.669% -13.190%] (p = 0.00 < 0.05)
                        Performance has improved.