PolymorphicVirtualCaster StaticObject instantiation takes a very long time at app startup

[ForestRingGames]

I recently updated to a newer version of cereal and it seems like some things have changed.

On startup Cereal creates these "StaticObject" instances now for every polymorphic registration.
My app now takes around 60 seconds to startup, compared to 1 second previously. I'm on iOS with an iPad Pro.

Why does this happen now?
What's the benefit of these StaticObjects?
Can I turn this off somehow?

[AzothAmmo]

cereal has always made these StaticObject objects for polymorphism support. Can you give us some more information - which version of cereal were you using before, and which version are you using now? Do you have profiling results which point to StaticObject as the source of the problem?

Is the behavior reproducible with a simple test case to isolate cereal as the cause of the problem?

[ForestRingGames]

Hmm Interesting....I'm using Xcode, so when I pause the application on startup to see what's taking so long, it's always busy initializing global variables - These StaticObjects.

I was using this version here: https://www.dropbox.com/sh/zutlvwslrqvfdwy/AACoCxAiiZYnB9rSBLTt_Usna?dl=0

I did some slight modifications to it in order to compile for the Android NDK (replace std::to_string)
Now, I tried using the latest version, I just downloaded as a zip file yesterday.

[AzothAmmo]

I'm not exactly sure which version that is since we don't include the version number in the source, but the biggest difference I can see is that the old version you were using was prior to us properly a detail related to dynamic casting between polymorphic types. This fix involved the creation of a new StaticObject, so potentially your issue is related to this, but I would need more information to either reproduce or know exactly which parts seem to be slowing you down.

Do you have a complicated class hierarchy at work, or a lot of polymorphic registrations? I can't think of anything we do that would cause such a dramatic increase in your runtime, unless there is some obscure edge case you are hitting.

[ForestRingGames]

Haha, yeah that's why I couldn't tell you the version.

Well, yes. I'm working on a strategy video game and implemented a custom Entity Component System. I'm registering every single entity and component class at the end of the header file. It's probably around 100 headers plus registering some multiple times (different template instantiations). In total it might be 200-300 registrations.

In the previous version, all is fine and I was super happy that cereal did such a great job (especially serializing between iOS and Android, which would have been very painful). But the new version is just unusable unfortunately.

I can't send you my huge project obviously....I could offer a skype call and show you how long it takes / let you step through my debugger if that helps.

[AzothAmmo]

Can you do me a favor and try the current development version of cereal? You'll have to clone it from github. If we are lucky it may already solve the problem, but I don't think that will be the case.

---

I think I can guess what is causing your problem, but I'll have to make a huge test case to see if I can reproduce it. If you can profile, I'm guessing the time is spent in PolymorphicVirtualCaster().

We fixed a bug related to polymorphism that required us to implement a way for cereal to know how to dynamic cast either direction in any polymorphic hierarchy. We get these relations automatically whenever you use something like cereal::base_class, but we also added in a new macro CEREAL_REGISTER_POLYMORPHIC_RELATION(Base, Derived) for cases when we can't figure it out.

One thing we try to do at initialization is to find all shortest paths of casting between polymorphic types. For example, you might have a hierarchy A->B->C, and let's say each one of those classes serializes its base, so we explicitly know the paths A<->B, and B<->C. We then try to see if we can do any of these transitions shorter, and discover that A->B->C can be reduced to A<->C.

Since you have so many registrations, I'm guessing that cereal spends a large amount of time trying to optimize these paths. The current algorithm is probably very inefficient, glancing at it it looks to be something like O(n^2) in the number of registrations.

---

Another workaround you can try, is in the newer version of cereal you already downloaded, comment out everything in PolymorphicVirtualCaster() after line 232 (the code dealing with finding chainable relations, see https://github.com/USCiLab/cereal/blob/master/include/cereal/details/polymorphic_impl.hpp#L232), and then fix any run-time errors you get along the lines of

unknown location(0): fatal error in "json_polymorphic": std::runtime_error: Trying to save a registered polymorphic type with an unregistered polymorphic cast.
Could not find a path to a base class (PolyBaseA) for type: PolyDerivedD
Make sure you either serialize the base class at some point via cereal::base_class or cereal::virtual_base_class.
Alternatively, manually register the association with CEREAL_REGISTER_POLYMORPHIC_RELATION.

by using CEREAL_REGISTER_POLYMORPHIC_RELATION as necessary.

[ForestRingGames]

@AzothAmmo
Sure, no problem. I just tried it and it did not fix the problem unfortunately.

---

It's interesting that you say that....I was facing many issues with Polymorphism recently...very often when I was trying to serialize a std::shared_ptr<BaseClass> and the actual object behind the pointer was like 5 class hierarchy steps away from BaseClass it would just crash, sometimes with Polymorphism errors. Sometimes saying, that DerivedClass was not aware of a path to DerivedClass. It was really weird. Sometimes it was thinking that DerivedClass wanted to serialize itself as with cereal::base_class. But other times it would just crash at a random point while deserializing. But I also got these errors with the version from yesterday. I fixed it now, but using a template serialization function that always uses the correct type of the class to serialize. This issue seems to only exist for the root node in a hierarchy. Hence, the std::shared_ptr that I put into the archiver needs to have the correct types, and then afterwards polymorphism seems to work.

Anyway....that's another issue. I might also open another ticket once this one here is sorted - just wanted to tell you that I've faced some of those.

---

Here's a Screenshot from the Xcode Time Profiler, profiling on an iPad Pro (hence the fastest device I currently target).

Since the Profiler performed a release build, the time it took went down drastically to around 2 seconds, instead of 30-60. But even with this, I would still opt for the old cereal version, since it will take 10 seconds at least on older Android devices.

These _cxx_global_var_init_ things show what's slowing it down so much on startup. I hope you can read something from it.

---

Removing the piece of code that you suggested lead to exactly the expected results: Super fast startup times, but Unregistered_Polymorphic_Exceptions.

[AzothAmmo]

I've already planned out an efficient algorithm to replace what we are currently using, and hopefully this will resolve the issue.

[AzothAmmo]

Try out the latest develop commit and see if this works for you, I haven't been able to test this on a large test case yet.

[ForestRingGames]

With this Version my App takes 38 seconds to start up on an iPad Pro.
With the previous version I was using it takes 3 seconds to start up.

I'm sorry to tell that it didn't help much.

[AzothAmmo]

Ok, I'll have to make a test case with a large number of classes to try and narrow this down. Right now we try to update the relations on every registration (since there is no way of knowing when registrations are done), but perhaps this could be deferred to either be manually done (e.g., in main), or the first time a serialization is done. Maybe this will be a compile time flag to control when this is done, I'm not sure yet.

[ForestRingGames]

Ah, so you mean that it is slow because it's trying to update the relations every single time for all registrations? Doing it one time in main might be super fast then?
Thanks for creating a test case and narrowing it down.

[AzothAmmo]

Yes, every time cereal gets a registration it tries to update all paths related to the registration. It basically traverses a tree (not technically a tree because of diamond inheritance) for the current class hierarchy being registered and updates all parent nodes with the shortest path to children. So it's not wasting a lot of time on unrelated registrations, but the deeper a class hierarchy is the more work must be done.

[ForestRingGames]

Okay, I see. So it shouldn't take too much time actually. It'll be interesting if not doing it for every registration would bring the time back down to 3 seconds instead of 30 or if it would be still like 5+ seconds.

If none of the improvements are of any help, I'd have to manually mark the parent / child relations right?

I'm definitely curious to see where this is going / what the solution might be, thanks again.

[AzothAmmo]

I'm trying to build a test for this - can you give me an idea of how many classes are in your hierarchies? How wide/deep are they, how many, etc. Approximates are fine, I just need to create a test case to hone in on this.

[ForestRingGames]

Sure: I'm registering around 200 classes and the typical depth is 5.

Of course some go deeper to 7-9 and some others only 2-3, but 5 is definitely the average.

Am 09.11.2016 um 23:34 schrieb Shane Grant notifications@github.com:

I'm trying to build a test for this - can you give me an idea of how many classes are in your hierarchies? How wide/deep are they, how many, etc. Approximates are fine, I just need to create a test case to hone in on this.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub #354 (comment), or mute the thread https://github.com/notifications/unsubscribe-auth/AUWZTCdbO2gA7DqP18CSjDH6LpqU82rWks5q8kpdgaJpZM4KZ96Q.

[ForestRingGames]

Hey, I just wanted to check back and ask if you've been able to get some kind of progress / improvement working yet. We're still using a very old version of cereal since we can't update due to the incredibly long startup time.

[cwlbraa]

@AzothAmmo We recently pulled in cereal's master branch and are experiencing similar issues as @ForestRingGames around startup, but with much beefier computers. I might be able to offer additional assistance tracking down the source of the slowdown.

We've got around 200 message classes as well (183-ish to be precise), almost all of which have only 1 or 2 parents. I've got some perf-based profiling working as well, and through that, on master, I can see an inordinately large amount of time being spent creating, erasing, and copying the red-black tree nodes underlying the polymorphic relation map https://github.com/USCiLab/cereal/blob/master/include/cereal/details/polymorphic_impl.hpp#L116

I'm not familiar with the evolution of the polymorphism feature, and it seems likely that that knowledge will lead to a better understanding of what changed, but one thing that strikes me is that an unordered_map might be more appropriate there...

But first, I'm going to run a compile and couple of experiments against develop and see if I get similar results.

[cwlbraa]

and as it turns out, your develop branch makes a big difference on my startup times [factor of 10ish], so it may be the depth or complexity of @ForestRingGames classgraph...

[AzothAmmo]

I can optimize the implementation further when I get around to making a test case. I haven't been working on cereal over the holidays but I'm going to make a push to close some issues and get the next release out soon.

[ForestRingGames]

@AzothAmmo Okay, sounds good! I can still offer you to do a skype session and show you the profiler running on my project to help you figure out what the issue is exactly. If you're up for that just message me via max {at} forestringgames {dot} com

[AzothAmmo]

There may be a solution to that as a result of #388, which I need to test. The downside to this solution is that it will require specificity when registering types, i.e. binding a polymorphic type to a specific type of archive, instead of it applying to any future archive.

I'm also curious to test boost under similar circumstances, since our implementation is a modified version of theirs.

I'm going to take the optimizations for runtime that are present here and push them to develop soon - there is likely room for future optimization but this is a good starting point for now.

[ForestRingGames]

I'd actually be fine with that. We're only using one type of archive anyway (BinaryPortable to be able to exchange the same data between all kinds of iOS and Android devices).

Testing boost would be interesting, before choosing cereal I wanted to try boost but it looked very heavy-weight and heard to get to compile for iOS and Android. I think it was a non-header-only lib of boost.

We're looking forward to test any possible improvement.

[ForestRingGames]

I forgot to ask: Do you know of any possible (hack-) fix, how we can avoid the huge memory usage on compiling? We'd just like to get the project to compile, so that we can start working with the windows machine. Is there maybe an old version that didn't have the issue or something similar?

[AzothAmmo]

It shouldn't be a big change, I can likely commit tomorrow. If my hunch is right on what causes the memory use, it will be present in all past versions of cereal (and also in boost).

…

-----Original Message----- From: "ForestRingGames" <notifications@github.com> Sent: ‎4/‎11/‎2017 4:22 PM To: "USCiLab/cereal" <cereal@noreply.github.com> Cc: "Shane Grant" <w.shane.grant@gmail.com>; "State change" <state_change@noreply.github.com> Subject: Re: [USCiLab/cereal] PolymorphicVirtualCaster StaticObjectinstantiation takes a very long time at app startup (#354) I forgot to ask: Do you know of any possible (hack-) fix, how we can avoid the huge memory usage on compiling? We'd just like to get the project to compile, so that we can start working with the windows machine. Is there maybe an old version that didn't have the issue or something similar? — You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub, or mute the thread.

[AzothAmmo]

This is going to take a bit more investigation than I thought - I just ran a single test showing 2x the memory use of boost for compilation, so the issue may be more nuanced.

[ForestRingGames]

Okay, thanks for the update.

Do you also see crazy memory consumption like 8+ GB for 300+ polymorphic registrations?
Do you think those segmentation errors that we face might be due to too much memory consumption?

[AzothAmmo]

It varies quite a bit depending on which test I run. I have one which does somewhere around 100 registrations against every archive type which uses at least 8GB, but the same registrations done against a single archive type are topping out at 2GB. I've never seen any adverse affect at runtime though (e.g. segfaults), but if you are getting segfaults with your compiler perhaps it is due to memory limitations.

[AzothAmmo]

I'm revisiting issues I had previously worked on and see that there were a few commits to develop based on the work here, but it's a bit unclear what the remaining issues are. Perhaps it would be best to open new tickets, link to this one, and close the discussion here.