NFD » ndn-cxx

None. The concept of ContiguousIterator was introduced in C++17, but there's no corresponding tag to identify them (http://en.cppreference.com/w/cpp/iterator/iterator_tags).
Regardless, my suggestion is don't bother, just document the requirement, or use a raw pointer.

Hmm. These are the numbers I see when running the benchmark (macOS, 2.3 GHz Intel Core i7). The new code slower...

Old code
size=1 offset=0 219556000 nanoseconds
size=3 offset=0 268252000 nanoseconds
size=3 offset=1 267114000 nanoseconds
size=5 offset=0 264818000 nanoseconds
size=5 offset=1 270172000 nanoseconds
size=5 offset=2 255616000 nanoseconds
size=5 offset=3 262931000 nanoseconds
size=9 offset=0 287426000 nanoseconds
size=9 offset=1 289188000 nanoseconds
size=9 offset=2 291034000 nanoseconds
size=9 offset=3 295733000 nanoseconds
size=9 offset=4 291629000 nanoseconds
size=9 offset=5 289105000 nanoseconds
size=9 offset=6 277025000 nanoseconds
size=9 offset=7 303509000 nanoseconds

New code
size=1 offset=0 215387000 nanoseconds
size=3 offset=0 337295000 nanoseconds
size=3 offset=1 328851000 nanoseconds
size=5 offset=0 347530000 nanoseconds
size=5 offset=1 344035000 nanoseconds
size=5 offset=2 361555000 nanoseconds
size=5 offset=3 358717000 nanoseconds
size=9 offset=0 347946000 nanoseconds
size=9 offset=1 343940000 nanoseconds
size=9 offset=2 334505000 nanoseconds
size=9 offset=3 347926000 nanoseconds
size=9 offset=4 328437000 nanoseconds
size=9 offset=5 348441000 nanoseconds
size=9 offset=6 333521000 nanoseconds
size=9 offset=7 348286000 nanoseconds

Alex Afanasyev wrote:

Hmm. These are the numbers I see when running the benchmark (macOS, 2.3 GHz Intel Core i7). The new code slower...

Did you build in release mode?

Intel Xeon CPU E5-2670 v2, Linux 4.9.20, gcc-4.9.4

OLD
size=1 offset=0 343432052 nanoseconds
size=3 offset=0 395435459 nanoseconds
size=3 offset=1 366619089 nanoseconds
size=5 offset=0 379292242 nanoseconds
size=5 offset=1 379371107 nanoseconds
size=5 offset=2 380444428 nanoseconds
size=5 offset=3 379511179 nanoseconds
size=9 offset=0 383363360 nanoseconds
size=9 offset=1 390663322 nanoseconds
size=9 offset=2 390677738 nanoseconds
size=9 offset=3 389844139 nanoseconds
size=9 offset=4 378852299 nanoseconds
size=9 offset=5 380164130 nanoseconds
size=9 offset=6 379236474 nanoseconds
size=9 offset=7 385322147 nanoseconds

NEW
size=1 offset=0 364241926 nanoseconds
size=3 offset=0 368986408 nanoseconds
size=3 offset=1 365006562 nanoseconds
size=5 offset=0 358115669 nanoseconds
size=5 offset=1 369409896 nanoseconds
size=5 offset=2 357927919 nanoseconds
size=5 offset=3 365090751 nanoseconds
size=9 offset=0 365555763 nanoseconds
size=9 offset=1 361008081 nanoseconds
size=9 offset=2 356402152 nanoseconds
size=9 offset=3 356399986 nanoseconds
size=9 offset=4 356410952 nanoseconds
size=9 offset=5 356396298 nanoseconds
size=9 offset=6 360957043 nanoseconds
size=9 offset=7 356505715 nanoseconds

Except for size=1, the new code is consistently faster.

Yes, optimized mode (./waf configure --with-tests). Repeated tests again with the same results as before (new a bit slower). Just in case, my "old" is 5f34d30e93b87b25e1cca14e91cfcacc9a0b8784 and "new" 11feffda993611dde4286934b7248816e8f13b37.

Alex Afanasyev wrote:

Yes, optimized mode (./waf configure --with-tests). Repeated tests again with the same results as before (new a bit slower). Just in case, my "old" is 5f34d30e93b87b25e1cca14e91cfcacc9a0b8784 and "new" 11feffda993611dde4286934b7248816e8f13b37.

Ok, I used exactly the same setup. I'll try with clang later.

Ubuntu 16.04 32-bit ./waf configure --enable-static --disable-shared --with-tests --without-pch --with-sanitizer=address,undefined
UBSan output for ndn-cxx:commit:81a088afbc249c50398d38f1cea77092cc95a830 has no complaint about misaligned access.

ubuntu@m0213:~/san-ndn-cxx$ build/unit-tests -t Encoding/TestTlv -l test_suite
Running 9 test cases...
Entering test suite "ndn-cxx Tests"
Entering test suite "Encoding"
Entering test suite "TestTlv"
Entering test suite "VarNumber"
Entering test case "SizeOf"
Leaving test case "SizeOf"; testing time: 156mks
Entering test case "Write"
Leaving test case "Write"; testing time: 183mks
Entering test case "ReadFromBuffer"
Leaving test case "ReadFromBuffer"; testing time: 490mks
Entering test case "ReadFromStream"
Leaving test case "ReadFromStream"; testing time: 422mks
Leaving test suite "VarNumber"
Entering test suite "NonNegativeInteger"
Entering test case "SizeOf"
Leaving test case "SizeOf"; testing time: 103mks
Entering test case "Write"
Leaving test case "Write"; testing time: 100mks
Entering test case "ReadFromBuffer"
Leaving test case "ReadFromBuffer"; testing time: 271mks
Entering test case "ReadFromStream"
Leaving test case "ReadFromStream"; testing time: 278mks
Leaving test suite "NonNegativeInteger"
Entering test suite "PrintHelpers"
Entering test case "PrintSignatureTypeValue"
/usr/include/boost/lexical_cast/detail/converter_lexical_streams.hpp:238:17: runtime error: downcast of address 0xbf82eaa4 which does not point to an object of type 'basic_unlockedbuf'
0xbf82eaa4: note: object is of type 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
  04 76 3b 14 28 76 3b 14  81 54 a0 b2 81 54 a0 b2  81 54 a0 b2 80 54 a0 b2  8c 54 a0 b2 80 56 a0 b2
              ^~~~~~~~~~~
              vptr for 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
/usr/include/boost/lexical_cast/detail/converter_lexical_streams.hpp:238:17: runtime error: downcast of address 0xbf82eaa4 which does not point to an object of type 'basic_unlockedbuf'
0xbf82eaa4: note: object is of type 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
  04 76 3b 14 28 76 3b 14  81 51 a0 b2 81 51 a0 b2  81 51 a0 b2 80 51 a0 b2  96 51 a0 b2 80 53 a0 b2
              ^~~~~~~~~~~
              vptr for 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
/usr/include/boost/lexical_cast/detail/converter_lexical_streams.hpp:238:17: runtime error: downcast of address 0xbf82eaa4 which does not point to an object of type 'basic_unlockedbuf'
0xbf82eaa4: note: object is of type 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
  04 76 3b 14 28 76 3b 14  81 4e a0 b2 81 4e a0 b2  81 4e a0 b2 80 4e a0 b2  98 4e a0 b2 80 50 a0 b2
              ^~~~~~~~~~~
              vptr for 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
../src/encoding/tlv.cpp:30:3: runtime error: load of value 4294967295, which is not a valid value for type 'SignatureTypeValue'
/usr/include/boost/lexical_cast/detail/converter_lexical_streams.hpp:238:17: runtime error: downcast of address 0xbf82eaa4 which does not point to an object of type 'basic_unlockedbuf'
0xbf82eaa4: note: object is of type 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
  04 76 3b 14 28 76 3b 14  81 4b a0 b2 81 4b a0 b2  81 4b a0 b2 80 4b a0 b2  96 4b a0 b2 80 4d a0 b2
              ^~~~~~~~~~~
              vptr for 'std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >'
Leaving test case "PrintSignatureTypeValue"; testing time: 1079mks
Leaving test suite "PrintHelpers"
Leaving test suite "TestTlv"
Leaving test suite "Encoding"
Leaving test suite "ndn-cxx Tests"

*** No errors detected

My benchmark on macOS 10.12 shows new code is 30% slower for 3-octet and larger VAR-NUMBERs.
./waf configure --enable-static --disable-shared --with-tests --without-osx-keychain

However, I think the Change still should be merged:

• For 3-octet VAR-NUMBER which experienced the greatest slowdown ratio, the absolute difference per thousand operations is 0.0022 milliseconds. I estimate no more than one thousand VAR-NUMBER decodings are needed when processing each packet, and 0.0022ms is too small to worry about.
• macOS is mainly used as end hosts, not routers. Performance is less critical on macOS.
• Benchmark in note-5 indicates the new code is consistently faster for all but 9-octet inputs on Linux, the usual platform for routers. 9-octet VAR-NUMBERs are not used in ndn-cxx, because TLV-TYPE is implemented as uint32_t which encodes to up to 5 octets, and the practical limit of packet size is 8800 octets so TLV-LENGTH is up to 3 octets.

Same linux system as note-8, this time using clang-4.0.1

OLD
size=1 offset=0 225139293 nanoseconds
size=3 offset=0 286069693 nanoseconds
size=3 offset=1 285300278 nanoseconds
size=5 offset=0 286577277 nanoseconds
size=5 offset=1 281542178 nanoseconds
size=5 offset=2 286274724 nanoseconds
size=5 offset=3 292053121 nanoseconds
size=9 offset=0 292926056 nanoseconds
size=9 offset=1 299447933 nanoseconds
size=9 offset=2 291830825 nanoseconds
size=9 offset=3 307051689 nanoseconds
size=9 offset=4 292697168 nanoseconds
size=9 offset=5 298853287 nanoseconds
size=9 offset=6 293802120 nanoseconds
size=9 offset=7 298033793 nanoseconds

NEW
size=1 offset=0 222543953 nanoseconds
size=3 offset=0 395634150 nanoseconds
size=3 offset=1 395043022 nanoseconds
size=5 offset=0 364022183 nanoseconds
size=5 offset=1 357715890 nanoseconds
size=5 offset=2 364271467 nanoseconds
size=5 offset=3 357249949 nanoseconds
size=9 offset=0 355419601 nanoseconds
size=9 offset=1 368415047 nanoseconds
size=9 offset=2 357166517 nanoseconds
size=9 offset=3 355884553 nanoseconds
size=9 offset=4 356522603 nanoseconds
size=9 offset=5 361962657 nanoseconds
size=9 offset=6 356480328 nanoseconds
size=9 offset=7 352119360 nanoseconds

The "new code" results with clang are consistent with those obtained with gcc. Notable exception is the case size=1, which doesn't use memcpy. The "old code" is somewhat faster with clang. This suggests that clang is able to optimize the non-memcpy code better than gcc (and better than the memcpy code).

Davide, what's your opinion on this? Proceed with the merge?

I'd agree with merging the change.