XKS speedup trickery

Lets have a look on how our traffic is XKey-scored and whether
its done with efficiency.

The XKS source seems to be some kind of mangled-C++, just like
a lot of C/C++-based languages exist for big/parallel
data processing (CUDA or other parallelizing extensions).

Given that, DB is obviously some kind of nested std::map or 
apparently of a derived type, as can be seen by the apply() 
member which is not part of a STL map.
Its probably not a multimap either, as denoted by the clear()
and in that [][] assignments are not possible with multimaps [1].

These types (as well as a multimap) are sorted associative
containers (dictionaries) who's lookup complexity is guaranteed
to be O(log(N)) at worst [2], where N denotes the number
of keys in the map. DB has at least 3 keys as seen from the 
snippet, but chances are that the number is much larger.The 
larger it is, the more need is for optimizing the map access.
I doubt that XKS has their own implementation of dictionaries
that have a better O() and are optimized in a way that
DB["tor_onion_survey"]["onion_count"]
access could be O(1). After all (look at the boost include), it
looks pretty much like STL-C++ code.

Given that, inside a loop the following XKS code is rather
inefficient:

for (values_t::const_iterator iter = VALUES.begin();
          iter != VALUES.end();
          ++iter) {
        DB["tor_onion_survey"]["onion_address"] = iter->address() + ".onion";
        if (iter->has_scheme())
          DB["tor_onion_survey"]["onion_scheme"] = iter->scheme();
        if (iter->has_port())
          DB["tor_onion_survey"]["onion_port"] = iter->port();
        DB["tor_onion_survey"]["onion_count"] = boost::lexical_cast(TOTAL_VALUE_COUNT);
        DB.apply();
        DB.clear();
      }
      return true;

because inside the loop, the STL's find-routine walks the DB map

4 times until it gets to DB["tor_onion_survey"]. Since the first 

key tor_onion_survey is static, it would be much better to keep

a cached iterator to save the lookup time in each cycle.

Additionally, the find for the second key again has O(log(N)),

where N seems to be 4 (onion_address, onion_scheme, onion_port 

and onion_count).

The loop should rather be organized like this:

      auto cit = DB_fast.begin();

        pair < string, map < string, string > > sm;

        sm.first = "tor_onion_survey";

        for (...) {

                sm.second["onion_address"] = iter->address() + ".onion";

                if (iter->has_scheme())

                  sm.second["onion_scheme"] = iter->scheme();

                if (iter->has_port())

                  sm.second["onion_port"] = iter->port();

                sm.second["onion_count"] = boost::lexical_cast(TOTAL_VALUE_COUNT);

                DB_fast.insert(cit, sm);

                DB_fast.apply();

                DB_fast.clear();

        }

The full speedup-demo with comparison of both methods can be

found here. The average speedup in my tests are about 30% which

can save a lot of tax payers money if the agency scales

their XKS horizontally. The speedup here is the O(1) access

via the pair<>, compared to the O(log(N)) access in the original

code via a map<>. And thats for a DB map that

just has N=1 (tor_onion_survey). In reality N should be much

larger.

Nevertheless C++ is a good choice for XKS for various reasons

and they seem to be learning-by-doing just like any other

coder out there.

Edit: Meanwhile I found another reason to avoid operator[]
for assignments in a row inside one of Scott Meyers excellent
books on C++ effectiveness [3] which I really recommend reading
to any XKS developers (there are also classes for it).

[1] The clear() is important for our later optimization, as
    insert() has the same semantics like operator[] assignment
    only if the key doesn't already exist - otherwise the
    assignment-step after finding the key won't happen with
    insert().

[2] Generic Programming and the STL, using and extending the C++

    Standard Template Library

    Matthew H. Austern, Addison Wesley, 1999,

    p.159f

[3] Effective STL, 50 Specific Ways to Improve Your Use of the
    Standard Template Library
    Scott Meyers, Addison Wesley, 2001,
    Item 24, p.106ff