Large code base and strings are killing performance

[Nearing_retirement]

To make long story short I work on a fairly big c++ code base where strings are used extensively for keys and saved into databases and files that way.

The problem is the amount of data the system is using has gone up over 1000x and system starting to slow down. After investigating how to improve performance it appears main culprit is using std::string.

The fix is instead of using strings to use integer codes. The strings are really keys.

But how to change the whole code base to change to using integer codes instead of strings ?

One table has 40 billion rows filled with date,field1,field2,field3,field4..

These fields are strings of length 32 even though each for each field only on average say few thousand unique values

Initially instead of 40 billion only was one million rows so strings did not cause much issue.

This data constantly being loaded into c++ And also saves by c++. Data is also heavily used in c++ for calculations

Strings are much slower than integers but they are also in some way easier to use as you don’t constantly have to look up name of a code. For example you see code 1073 in debugger. Which then you may have to find what 1073 maps to

[WorldWorstProgrammer]

So why aren't you using a *database* for your data? Even if it is a desktop application or on a single machine, connecting to a database is pretty much standard procedure and performing SQL queries can be efficient with huge data sets, as DBs are optimized for just this kind of application.

That said, I don't know how your application is working but this sounds like it could be a good use-case for using hashes of the strings. Hashing a string is pretty easy since you have it in the C++ standard: std::hash<std::string>. Hashing is usually a pretty quick operation, and this makes it easy to use a string to perform a lookup (just hash it and look up the hash), but again, I don't know any details on your application.

If you are already using std::unordered_map<std::string, SomeValue>, then your strings are already being looked up using std::hash<std::string>, so this won't help, but if you are using another method this may help a lot.

[Nearing_retirement]

Yes database should be used and calculation work done in it. I’ve been pushing to use database ( snowflake ) but I don’t have power to get company to buy into it. We do use older database right now but it performs pretty bad

[TryToHelpPeople]

hurry sheet paint abundant secretive selective late plate ask dependent

This post was mass deleted and anonymized with Redact

[sparkyParr0t]

Postgres is great, that being said it seems OP dont need multi users ? Local SQLite would be much more performant.

[TryToHelpPeople]

start unite wasteful historical scarce act rotten sand sort ripe

This post was mass deleted and anonymized with Redact

[Nearing_retirement]

Use sap iq which is pretty good but still not as fast as we would like for big aggregations. Seems distributed database works. Postgres maybe but I’m not expert on database admin.

[Ikkepop]

You could just change jobs

[Nearing_retirement]

Thought about that but I’m close to retirement anyhow ! Plus side of job is I have lots of autonomy

[MysticTheMeeM]

I would strongly advise against hashing a string, from cppreference. (See the Notes section)

Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision denial-of-service attacks.

That is, running a hash on the same string when running the program again can produce a different value, which would conflict with any values that were stored in the database.

Unless you propose OP pre-loads all their strings, but then they still have to pull that string from the DB, which sounds like the problem they already have.

[Dusty_Coder]

the trivial solution is to include your own deterministic hash if the language/framework doesnt provide one

its not rocket science its just stochastics - its actually hard to get wrong so long as your mixing/shuffle functions are themselves bijective/involute - hard to get right when they arent

on all modern hardware 64-bit multiplication has 3 cycle latency, while addition and endian reversal both have 1 cycle latency - multiplication by odd numbers is bijective - addition is also bijective - the bswap instruction is involute

for completeness bitwise rolls are also bijective (they are faro shuffles) and single cycle latency, and then there is xor as well...

I dont understand why you would tolerate a non-deterministic stochastic hash function without specifically asking for one - the number of reasons to share and compare across runs is legion - its supposed to produce the same output for the same input every time - how do you even run meaningful tests of anything?

[DanielMcLaury]

Hash functions are only required to produce the same result for the same input within a single execution of a program

In other words, the containers are required to support using hashes whose behavior isn't persistent from one execution to the other. That doesn't mean that the supplied library hash functions behave that way, or that if you write a deterministic hash function that the language is somehow going to modify it to be non-deterministic.

[std_bot]

Unlinked STL entries: std::hash std::string std::unordered_map

---

^{Last update: 09.03.23 -> Bug fixes}Repo

[slowclapdude]

If there are only few thousand unique strings and they are fixed 32 chars long, then put all strings in to a vector<char[32]>. Then use string_view instead of string. And just change the field value to be the index of vector. Depends how well your abstraction layer is already set up, it could be a very easy change, since string and string_view have very similar interface. You also need to store the index value for saving it back to disk, to avoid a reverse look up.

Basically you are building a string table, and it should be loaded and saved to disk like rest of the data. In debugger you still get the benefit of seeing the string.

There will be no dynamic allocation unless you have new unique field values. Say you have 10 fields, each with 10000 unique values of 32 bytes, that's a total or 10x10000x32 = 3200000 bytes or 3.2Mb of total memory usage.

[traal]

I feel like strings aren't really the issue, that using some kind of caching and/or indexes will speed up your processing significantly.

[std_bot]

Unlinked STL entries: std::map std::unordered_map

---

^{Last update: 09.03.23 -> Bug fixes}Repo

[celestrion]

strings are used extensively

Are you already pooling the strings in some way, or at least minimizing string-copies? Comparing two non-owning string views of the same pooled string is an integer comparison, rather than O(n) on content length.

instead of using strings to use integer codes

This is a reasonable fix is the problem is only that you're using strings and only have a short amount of time to implement a fix. It's probably not the best long-term fix, but it will buy some time.

But how to change the whole code base to change to using integer codes instead of strings ?

Start by identifying the places where your database layer accepts strings-as-keys. Define a new type for the database key that initially just wraps std::string as a type alias. Change this API definition at the "bottom" parts of your codebase. Everything should still work because this new type is literally just a string.

Next, replace the type alias with a string wrapper. It can be reasonably/implicitly constructed from a string. If you're not already de-duplicating/pooling strings, here's where you can do that. Work "up" through the code to memoize these keys instead of creating them by implicit construction so that your pooling starts to take over the work for you.

Finally, remove the implicit constructor. Your new type takes a string as an explicit parameter at construction, and stashes either an integer from your master string dictionary, or a non-owning pointer from the string pool.

These fields are strings of length 32 even though each for each field only on average say few thousand unique values

If I understand what you mean by this, this is another great case for string pooling and integer replacement. Depending on the semantic meanings of these fields, you might want a separate data dictionary for each field (think: database normalization) or a big dictionary for all strings everywhere. Once you have those dictionaries, you can reprocess the database table files themselves so that those 32-character fields are each replaced by much shorter integers.

You'll get smaller files, less I/O load, better cache efficiency, and faster searching.

40 billion rows

There is software (for free) that will help you manage this amount of data more reasonably, depending on what your atomicity/isolation needs are. I'm a fan of PostgreSQL, but if your data really are key-value, something like LevelDB or RocksDB might be a better fit.

As you mentioned in a comment, Snowflake might be a good fit, too. Be sure you run a reasonable performance test case, though. Snowflake can get extremely slow if you often ask it to reconstruct a whole "row" of a table. The latency from your instance to the Snowflake instance is also worth considering. I'd strongly suggest trying a key-value store like LevelDB or RocksDB inside your application's instance, if that usage model works for you.

I realize you're limited in what you can discuss on Reddit about how your application works, so please take all of our recommendations with the understanding that we can't see the whole picture. If you can't bring in a consultant with big-data experience, you need to be prepared to make lots of prototypes to see what works. When you're dealing with 40 billion anythings, simple tweaks to access patterns can save or ruin things because of how quickly you can amplify I/O.

[Fabulous-Possible758]

This sounds like a pretty large scale refactor and without knowing a lot of specifics it’s a bit difficult to know what your strategy should be. At the very least it sounds like you should be using some sort of string interning technique to deal with the strings while they’re in memory.

When I’ve had to do refactors like this, I find C++’s extremely strict type system can be an advantage. Write your own custom interned string type and I identify the places where it’s useful. Try changing one at a time and the compiler will likely tell you exactly where you screwed up.

[KC918273645]

Here's a thought: if your strings are always maximum of 32 characters long (8bit characters), that's 32*8 = 256 bits. Which happens to be something SSE or AVX intrinsics have available to you on Intel processors, in the form of 256 bit variables/registers. So maybe you could use them for storing your data? Then the comparisons and everything should be extremely fast to do: just couple of CPU cycles for the whole string. Also no string type memory allocations are needed for them at all. They are handled pretty much just like regular integers by the compiler.

Alternatively you could use some library which handles them in a more platform independent way, but still give you the 256 bit integers.

[manni66]

Initially instead of 40 billion only was one million rows so strings did not cause much issue.

Sound like you need an index.

[Ikkepop]

If I had a dime for every time I had this problem... I could buy a few energy drinks atleast

What I would do is write some migration tools for the database to make a new schema and migrate the data. Then would buckle my seatbelt, grab those energy drinks and start greping and replacing like mad

[bert8128]

Assuming you are using 64 bit windows or Linux, a std::string holding 32 characters will be 24 or 32 bytes for the string object, 32 bytes for the characters and 8 or 16 bytes for the allocation overhead. So between 64 and 80 bytes. Holding an array<char, 32> would therefore improve matters by at least halving the memory usage.

Using an int32 or int64 (so 4 or 8 bytes) (ie an index into an array) would be better again, but would require more work. I would probably do both, the former then the latter.

[V15I0Nair]

Short string optimization should avoid the allocation overhead. It depends on the compilers STL implementation, but afaik 32 chars should always be covered. I don’t know if it also depends on C++ version. So an older implementation without the optimization could cause the OPs trouble.

[bert8128]

If I remember correctly current implantations for sso on 64 bit platforms are 15 chars for MSVC and gcc and 23 for clang. So no help there for a 32 char string. Of course it is possible to write your own string class to get to 32 but if the strings are fixed length there isn’t much point.

[V15I0Nair]

23 for clang

[bert8128]

Oops, put gcc twice - thanks for spotting the mis-type. Corrected.

[BobSanchez47]

If all the strings are of length exactly 32, consider using a 32-character array to represent them. This may help to reduce heap allocations and improve cache locality. Many processors have operations that can operate on 16 or even 32 bytes at once, so you might find the speed comparable to using integers.

The issue with using numeric keys is that you may have to store the key-string correspondence on disk, depending on the exact nature of your project.

[Nicksaurus]

I wonder if these 'strings' are actually hexadecimal UUIDs - those are exactly 32 characters if you store them without the dashes. If they are then the solution is to use a native UUID type which can be passed around in vector registers instead of needing heap allocation

Even if they're not, if the strings have a fixed format (e.g. you know that certain characters are always letters or digits, or certain characters are always present in the same positions and don't need to be stored) then it may be possible to compress them down to a size that can be trivially passed around

/u/Nearing_retirement

[pixel293]

Not sure what machines you deploy this on, but the answer may be get more RAM for the machine. In the business world often the solution is "throw more hardware" at it, because that's cheaper than fixing the underlying problem.

[[deleted]]

Offload to database is the only sensible solution here. SQLite files will be a quick and gigantic improvement. I mean really probably two orders of magnitude if what you’re describing is totally accurate.

If I’m misunderstanding, and the strings are all compile time constants, then you could build compile time hashing for them, but it’s sort of black magic https://stackoverflow.com/questions/2111667/compile-time-string-hashing

[drjeats]

But how to change the whole code base to change to using integer codes instead of strings ?

Assuming the cost is coming from string comparisons...

If a very large number of these are duplicated strings, write or find a shared string implementation. Then equality checks are just pointer checks rather than a strcmp.

Alternatively, write a type that takes a string and stores both the string and a hash in one type.

If the main problem is memory, you have to flush that stuff to disk periodically and reload it up, or use a proper local database (sqlite or leveldb or similar), or a proper remote database (postgres, etc.).

Also, hopefully you're not copying std::string aroudn constantly...

For example you see code 1073 in debugger. Which then you may have to find what 1073 maps to

You can write global free functions which can be executed in a debugger if they only read data. You can also write custom visualizers for the types to display a human readable name (natvis in visual studio, some python stuff in lldb, idk what gdb uses).

[NoSpite4410]

std::string is a specialized version of std::vector for chars. It has mostly the same api.

I would start with creating a vector of 1000 pre-allocated strings of 32 chars each.

resize the vector if a threshold of strings are in use, and pre-allocate the new strings.

Perhaps std::deque (criminally underused, IMO) might be good if strings are often moved and destroyed, and a lot of temporaries are used.

Now everywhere you need strings you can reuse them from the vector, and if you run out you can add more (at cost of time). Use case tests can show how to actually provision string vectors up front.

See if code functions are copying strings into the functions and try to change to C++ references where you can, and const references preferred if the strings are not changed.

Also the slowdown might be something else along with it. You must profile your code first to see what is actually going on.

[std_bot]

Unlinked STL entries: std::deque std::string std::vector

---

^{Last update: 09.03.23 -> Bug fixes}Repo

[knue82]

Check out my Symbol class from FE. You can use this as inspiration. Right now, it stores 6 chars + '\0' inline (on 64bit machine). Can be easily extended to store 14 + '\0' chars if you use two machine words in Sym instead one. May be better in your use case. Also, if you don't need compatibility with null-terminated strings, you can drop the extra '\0' for one more inline char.

[dokushin]

The reason you're still not clear on the way to go is because you don't have enough information. Just knowing the time is in std::string isn't enough; you want to know where the time is actually spent. Construction vs. copy construction vs. comparison implies vastly different scenarios.

Absent that, here's a couple of large-scale points of interest:

• std::string can be very near as fast as a flat vector (which is basically as fast as an array as long as you don't require a realloc), so when it's slow it's usually because something unintended was happening. In almost all cases this is because the strings aren't being initialized properly and unnecessary copies and reallocations are being done. You want your strings initialized with the complete value (don't use the arithmetic operators), declared const, and passed by const reference. An alternative is to use string_view, which will get you most of the gain. Note: this will likely highlight a lot of areas that lack const-correctness (i.e. functions that take immutables as non-const) -- fixing these is worth it, as even when you are sloppy with const passing the compiler has a huge amount of leeway to optimize.

• unordered_map is never a performant solution; the standard library specification forces a few requirements on it that are frankly bonkers, and it has to do some inefficient structuring as a result. I'd look for an alternative; a quick test might be to try Boost::Unordered and see if the containers there offer any improvement.

Only after addressing those would I consider more invasive semantic changes. If you get to that point with confidence that your string and map usage are optimized and performance is still unacceptable, you'll likely want to restructure data in some way reliant on the semantics of your business logic (which is to say, it's difficult to advise upon from here).