How to quicken a table look up?

[MikeStgt]

As I am a beginner I ask in the beginners forum. But the question might be something for experts.

The only reason (up to now) why I am engaged in C++ is to modify an existing program, a virtual HP41. I was not happy with the layout of the trace log. I managed to change it, but I also added some more labels (named entry points) known from firmware listings. V41.exe as published contains a list of almost 800 labels, mine nearly 3000 what slows down the trace option noticeable.

Question: How may I speed up the table lookup?
Currently for every CPU cycle of the virtual HP41 the complete list is scanned to see if the address has a label. For far jumps (XEQ and GTO) it is even scanned twice as the log will show the label of the destination.

Currently I have two options in mind,i) distribute the 3000 labels to several lists, for example 11 lists, get the PC (program pointer or address pointer) modulo 11 and scann only the corresponding list. Now every single list is less than 300, so the gain should be about 10 times faster. Instead of modulo 11 I could do modulo 16 what is the last nybble of the PC, but then the size of the labels' tables is not so equally in size.

Or ii) I keep the list of 3000 labels and spend 4k for a vector<bool> with a flag set for each label-tagged address. Then I have to scann the list only for those addresses. The 3000 labels derive from 12k OS and 8k HPIL-ROM, so the ratio untagged/tagged is 5.8:1 what is less than the 10x of option i) But! - maintaining the list is much simpler, if someone in future wants to add the labels of another address bound ROM.

More ideas? Other options? What's your proposal? Every hint is welcome.

M.

Edit: clarified one sentence

[dutch]

Can't you do a binary search of the list? And you could have the flags, too.

What exactly does a table entry look like?

[Duthomhas]

Alas, I don’t think it is very likely you are going to find anyone lurking here that knows anything about the HP41 emulator source code.

At heart, a lookup table is simply an indexed array/vector/whatever. The index into the table is a simple counting number that is easy to keep or compute. This makes an O(1) access.

What it sounds like is that your table is being searched for a matching string. That’s two strikes. First, it is searching the table (sounds like a linear search?). Second, it is comparing strings. This has suddenly become a very expensive operation.

If the only thing you do is sort the lookup table (and keep it sorted), then use a binary search, then you will see significant speed up.

But if you really want to get that thing to squeak, you should be using a hash table lookup.

I recommend a sorted table and binary lookup first. This will be nicest for your peace of mind and easy to implement without breaking existing code. Only if it remains too slow (it won’t for only 3000 labels) do you need to consider turning your table search into a bona-fide hash lookup.

Hope this helps.

[salem c]

> distribute the 3000 labels to several lists,
If you sort by address, you can achieve a binary search in just 12 operations.
http://www.cplusplus.com/reference/algorithm/binary_search/

[MikeStgt]

What exactly does a table entry look like?

Excerpt from HP41Trace.cpp:

...
#define Globals 2916

...

struct Glob_type          // Global routines names
  {
  char name[NameSize];    //name
  word addr;              //address
  };

...

struct Glob_type GlobalName[Globals]=
{
  "ADRFCH",0X0004,
  "OVRSTK",0X0018,
  "FCHRTN",0X0020,
  "X<>ROW",0X0026,
  "XROW0",0X002F,
  "XROW10",0X0031,
...

  "POWOFP",0X7FF7,
  "I/OSVP",0X7FF8,
  "DEEPSP",0X7FF9,
  "COLDSP",0X7FFA,
  "PRTID",0X7FFB,
  "CKSUMP",0X7FFF,
};

...

void HP41::FindGlobalName(uint addr, char *name)
{
	name[0]=0;
	for(int i=0; i<Globals; i++)
	{
		if(GlobalName[i].addr == addr)
		{
			strcpy(name,GlobalName[i].name);
			break;
		}
	}
}

...

uint HP41::FindGlobalAddr(char *name)
{
  char name2[50];
  sprintf(name2,"[%s]",name);
  for(int i=0; i<Globals; i++)
  {
    if(0==strcmpi(GlobalName[i].name,name2))
      return(GlobalName[i].addr);
  }
  return(0);
}

FindGlobalAddr is only called when defining break point by label. That is used rarely (and buggy). I have sorted the list by address, and yes, the binary search could be the best solution.

... you should be using a hash table lookup.

What I described as option i) is a hash table lookup as I understand it, with (address % 11) as my "hash function". So the 11 "buckets" contain about 270 elements.

Thank you all who answered.

[JLBorges]

> More ideas? Other options? What's your proposal?

Using Boost.Bimap https://www.boost.org/doc/libs/1_69_0/libs/bimap/doc/html/index.html#bimap.preface
is a possibility. For example:

#include <iostream>
#include <string>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <cstdint>
#include <iomanip>

using namespace boost::bimaps ;

struct name_tag {};
struct address_tag {};
using DWORD = std::uint32_t ;

using name_address_map_type = bimap< unordered_set_of< tagged<std::string,name_tag> >,
                                     unordered_set_of< tagged<DWORD,address_tag> > >;

const name_address_map_type& name_address_map()
{
    static const name_address_map_type::value_type entries[] =
    {
          { "ADRFCH", 0X0004 },
          { "OVRSTK", 0X0018 },
          { "FCHRTN", 0X0020 },
          { "X<>ROW", 0X0026 },
          { "XROW0", 0X002F },
          { "XROW10", 0X0031 },
        // ...
          { "POWOFP", 0X7FF7 },
          { "I/OSVP", 0X7FF8 },
          { "DEEPSP", 0X7FF9 },
          { "COLDSP", 0X7FFA },
          { "PRTID", 0X7FFB },
          { "CKSUMP", 0X7FFF },
    };

    static const name_address_map_type map { std::begin(entries), std::end(entries) } ;
    return map ;
}

const std::string& find_global_name( DWORD address )
{
    static const name_address_map_type& map = name_address_map() ;
    static const auto view = map.by<address_tag>() ;
    static const std::string nothing ; // return this (empty) string if entry is not found

    const auto iter = view.find(address) ;
    return iter != view.end() ? iter->get<name_tag>() : nothing ;
}

DWORD find_global_address( const std::string& name )
{
    static const name_address_map_type& map = name_address_map() ;
    static const auto view = map.by<name_tag>() ;

    const auto iter = view.find(name) ;
    return iter != view.end() ? iter->get<address_tag>() : 0 ; // return zero if entry is not found
}

int main()
{
    std::cout << std::hex << std::showbase << std::uppercase << std::internal << std::setfill('0') ;

    for( DWORD addr : { 0X0018, 0X7FF8, 0X0026, 0XABCD } )
        std::cout << std::setw(6) << addr << " => " << std::quoted( find_global_name(addr) ) << '\n' ;

    std::cout << '\n' ;

    for( std::string name : { "OVRSTK", "I/OSVP", "X<>ROW", "no such name" } )
        std::cout << std::quoted(name) << " => " << std::setw(6) << find_global_address(name) << '\n' ;
}

http://coliru.stacked-crooked.com/a/3d464ab5b7f9e439

[MikeStgt]

Thank you for your time and effort for the working example. I am just about to copy it into my cpp to test it. I'll keep you posted.

Update: Have some trouble to install that lib.

Specific steps for setting up #include paths in Microsoft Visual Studio follow later in this document

Alas not found yet.

[MikeStgt]

Sorry, I am stalled at installing Boost library to use it with VS2010.
What I did: downloaded https://dl.bintray.com/boostorg/release/1.69.0/source/boost_1_69_0.7z, compared the SHA256 Hash (is ok), unpacked it, opended the index.html that comes with it, found in 'Getting Started on Windows' that for header-only libs there's nothing to build. So I moved the complete boost directory to C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\atlmfc\include so VS may find it.
Next I tested the

#include <boost/lambda/lambda.hpp>
#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
    using namespace boost::lambda;
    typedef std::istream_iterator<int> in;

    std::for_each(
        in(std::cin), in(), std::cout << (_1 * 3) << " " );
}

Runs on http://www.cpp.sh/ alas under VS2010 I get

1>c:\program files (x86)\microsoft visual studio 10.0\vc\atlmfc\include\boost\lambda\core.hpp(27): fatal error C1083: Cannot open include file: 'boost/type_traits/transform_traits.hpp': No such file or directory

but the file is in the directory as requested. Documentation contains a lot of information, may be I overlook the essential.

[JLBorges]

Why are you trying to use Visual Studio 2010? Is it an inviolable project requirement?

[Duthomhas]

Installing Boost on Windows is a pain.

First, make sure you unzip it in a good spot.

IDR whether the hash maps stuff in Boost need compiling, but some parts of boost do need it. If you want to compile those parts, you will need to find and download a pre-compiled bjam.exe. (I have never managed to compile it myself on Windows.) Then follow the basic configure and compile steps as described in the documentation.

Once that is done, then you need to let your compiler know where to find the headers (and libraries). In MSVC this is typically (and expected to be) done on a per-project basis. (You can do this globally, and for something like Boost I don’t see that as a problem. But Microsoft has good raisins for wanting you to do it per-project.)


Library Path
I will personally move all the compiled stuff (.dll and .lib/.a) stuff directly into an appropriate directory structure, part of where I keep all my external MSVC libraries:

    C:\MSVC\libs\boost\all
    C:\MSVC\libs\boost\dynamic
    C:\MSVC\libs\boost\static
 
I also personally delete all the debug stuff. I don’t need to debug Boost’s libraries.

I will also rename the library files so that they are common^[1]. That way I can go to the MSVC/project options and add the correct lib directory to the library includes path. Then I can use the common name for the desired library, for example:

#pragma comment( lib, "libboost_system" ) 

[1] This is because Boost will compile to .lib/.a names that are garbled with additional information: this is a debug version, this is a static version, this is a... etc.

(I actually have a single directory for these —all— everything in the other directories are hard links to the correct lib file. That way I can just specify a library path that matches the project options. This is pretty easy to do with a for DOS command.)


Include Path
I will also move the include directory to a proper space:

    C:\MSVC\include\boost

Then, in the MSVC/project options I will add the C:\MSVC\include directory to the includes path.^[2]

[2] This is what I think you are missing. Make sure to update the includes path to find the boost include directory, which should be named “boost” (not “include”, as it is by default when you unzip boost). Hence my renaming step above.

That way you can properly #include stuff, and the compiler can properly find it:

#include <boost/type_traits/transform_traits.hpp> 

Hope this helps.

[MikeStgt]

Thank you very much for your detailt description. I'll give it a try ASAP, not tomorrow, it will be a busy day with something a little more important than C++ (sorry).

[Duthomhas]

I forgot to mention that compiling Boost takes a while. Make sure you have an evening to deal with it.

Also, I hope all goes well with you.

[MikeStgt]

Why are you trying to use Visual Studio 2010? Is it an inviolable project requirement?

In which hidden manner are your two questions related to the subject How to quicken a table look up? If you want to tell me, do not use MSVS then everything is two times faster, why do you put this message in questions?
Since 2..3 weeks I do my very first steps with C++, I am interested in procedures, not in tools. I prefere solutions not problems.

[Duthomhas]

JLBorges is not trying to be sneaky. He is very direct, and sometimes not very tactful. He also is not a huge MS fan.

But he is asking for a good reason: VS2010 is outdated software. You can easily upgrade to VS2017, which is significantly upgraded in more than a few ways; in particular, its conformance to C++ language standards is much better.

If you were using the latest VS, it would make his answer easier, because then he wouldn’t have to worry as much about giving you a solution that simply wouldn’t work for you.

That’s all he means.

[salem c]

That escalated quickly.

Simple lookup - install boost.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

typedef unsigned short word;
const int NameSize = 10;
const int Globals = 2916;

struct Glob_type          // Global routines names
  {
  char name[NameSize];    //name
  word addr;              //address
  };

struct Glob_type GlobalName[Globals];

void init() {
    for ( word i = 0 ; i < Globals ; i++ ) {
        snprintf(GlobalName[i].name,NameSize,"Lbl %d",i);
        GlobalName[i].addr = i * 10;
    }
}

int cmp(const void *a, const void *b) {
    const Glob_type *pa = reinterpret_cast<const Glob_type*>(a);
    const Glob_type *pb = reinterpret_cast<const Glob_type*>(b);
    if ( pa->addr < pb->addr ) return -1;
    if ( pa->addr > pb->addr ) return +1;
    return 0;
}

const Glob_type *finder(word addr) {
    Glob_type key = { "", addr };
    void *result = bsearch(&key,GlobalName,Globals,sizeof(Glob_type),cmp);
    return reinterpret_cast<const Glob_type*>(result);
}

int main(int argc, char* argv[])
{
    init();
    int hits = 0;
    auto c1 = clock();
    for ( int i = 0 ; i < 1000000 ; i++ ) {
        const Glob_type *r = finder(rand()%32000);
        if ( r ) {
            hits++;
        }
    }
    auto c2 = clock();
    std::cout << "Total hits=" << hits << std::endl;
    double elapsed = double((c2-c1)) / CLOCKS_PER_SEC;
    std::cout << "Elapsed=" << elapsed << std::endl;
    return 0;
}

[MikeStgt]

Also, I hope all goes well with you.

Thank you.

JLBorges is not trying to be sneaky.

I saw that

(11872)

behind his name and for a moment I was not sure if I as amateur should reply in that blunt manner or not. But I was a bit annoyed or astonished or displeased that obviously VS2010 seems not be something to do binary search or hash table lookup or similar stuff. I regard it like going on holiday by plane or SUV or push bike, neither the speed nor the distance, the joy it is important.

Another aspect: my major interest is foremost about ancient emulated or simulated or let's say virtual calculators at most several decades old. Some kind of nostalgia. So why not use obsolte software to compile those emulators? A high esteemed contributor still developes for DOS. What he does works flawlessly under DOSBox. Well, it works as role model, a shiny surface is today an important part of an application.

Now we have a subject drift I disklike. My fault, I know. I try to get Boost to work for me this week, then (if Bimap offers a faster lookup) this thread will get a green checkmark and that's it. Right?

[Duthomhas]

I have to agree with salem c. You are going through a lot of trouble to mess with Boost.
Remember how I suggested you simply keep your table sorted and use a binary search? It would work lickety-split, and save you all the grief of messing with hash-maps and code refactoring.

[jonnin]

sorry, latecomer here, is this the table you are looking up into?

static const name_address_map_type::value_type entries[] =
{
{ "ADRFCH", 0X0004 },
{ "OVRSTK", 0X0018 },
{ "FCHRTN", 0X0020 },
{ "X<>ROW", 0X0026 },
{ "XROW0", 0X002F },
{ "XROW10", 0X0031 },
// ...
{ "POWOFP", 0X7FF7 },
{ "I/OSVP", 0X7FF8 },
{ "DEEPSP", 0X7FF9 },
{ "COLDSP", 0X7FFA },
{ "PRTID", 0X7FFB },
{ "CKSUMP", 0X7FFF },
};

take a look. every single one of those strings is < 8 bytes long.
that means you can cast them into a 64 bit integer and avoid string comparisons.
it likely also means that you can numerically hash them into a O(1) lookup table.
Don't need boost or a binary search if this is your data, just some legwork to come up with a good hash.

[MikeStgt]

sorry, latecomer here

No problem, the code runs untoched sice years, one..two weeks more are no harm.

is this the table you are looking up into?

Yes it is. A short glance into your proposal and those of others here, I consider to look at the table the other way round: the address is unique, there are never two or more labels assosiated with any address. This said, I limagine something like an array with the address as index and the content is the label as string. This will be an array with gaps, all not listed adresses do not have a label. Such kind of arrays are possible as stem in REXX and ooREXX, or as array in ooREXX. Other languages probably too, C++ too (with the same functionality as REXX?).
So far as I had time for this idea, I assume in C++ map or unordered_map could do what I am looking for. If trace is on, for every CPU cycle of the HP41, the table is queried if there is a lable for the currend address, if yes, the trace output is complemented with it. As this table lookup is executed for each and every executed address (for long jumps also for the destination) it should be as fast as possible. In contrast, the query for the address of an label is rarely needed, only when the user sets a breakpoint by label instead of address. If this "reverse lookup" is faster than 0.2 seconds I regard it as quick enough.

Now back to something more important...

[jonnin]

unordered map is faster, I believe, for this kind of work.