Speedup c median filter #2921

pull Enelar wants to merge 3 commits into bitcoin:master from Enelar:speedup-CMedianFilter changing 1 files +28 −16

Enelar commented at 5:00 AM on August 21, 2013: none

By the defer calculating sorted values we gaining speed on multiply numbers insert.

google translate: using a deferred calculation, we've increased the speed of insertion of several numbers in succession

Optimization TimingResistantEqual

Time of comparison proportional length of shorter argument. Less
operations on cycle. (Removing weight % operation).

1621da0459

Speedup CMedianFilter

By the defer `rendering` of sorted values we gaining speed on multiply
numbers insert.

328433fbd5

Skip copying arrays on constant usage

Maybe, someone need to use sorted().size(), for that, he dont need
copying constructor

ee78b6c529

BitcoinPullTester commented at 5:36 AM on August 21, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/ee78b6c5292a6613d33223761c9a2548d936bd77 for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.
gavinandresen commented at 6:10 AM on August 21, 2013: contributor

NACK on the TimingResistantEqual optimization-- new version lets an attacker determine the length of the password.

RE: optimizations in general: NACK unless you have a use case where performance matters. If you do, then please share what is sped up, and by how much.
Enelar commented at 6:16 AM on August 21, 2013: none

Got it. What about my commentary about the reset of the median filter. Is this a bug?

gavinandresen commented at 7:52 AM on August 21, 2013: contributor

CMedianFilter works correctly for me (patch for the median filter unit test):

diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp
index abfd882..be4b2d3 100644
--- a/src/test/util_tests.cpp
+++ b/src/test/util_tests.cpp
@@ -32,6 +32,12 @@ BOOST_AUTO_TEST_CASE(util_criticalsection)

 BOOST_AUTO_TEST_CASE(util_MedianFilter)
 {
+    CMedianFilter<int> filter2(2, 0);
+    BOOST_CHECK_EQUAL(filter2.median(), 0);
+    filter2.input(10);
+    filter2.input(20);
+    BOOST_CHECK_EQUAL(filter2.median(), 15);
+
     CMedianFilter<int> filter(5, 15);

     BOOST_CHECK_EQUAL(filter.median(), 15);

gavinandresen closed this on Aug 22, 2013
laanwj commented at 5:33 AM on August 22, 2013: member

The median filter is only used on new connections and is used with very small filter sizes. It's deliberately very simple in implementation.
DrahtBot locked this on Sep 8, 2021

Contributors