How to speedup instances operations?

Discussion related to the LuxCore functionality, implementations and API.
User avatar
Dade
Developer
Developer
Posts: 5672
Joined: Mon Dec 04, 2017 8:36 pm
Location: Italy

Re: How to speedup instances operations?

Post by Dade »

I optimized the implementation of Scene::DeleteObjects() (and added the support to Python API): it is now more than 4 times faster deleting over 1,000,000 of objects (it takes less than 1 second). The complexity is now O(n) instead of O(n^2) so more objects you have and faster it is.
Support LuxCoreRender project with salts and bounties
User avatar
TAO
Developer
Developer
Posts: 850
Joined: Sun Mar 24, 2019 4:49 pm
Location: France
Contact:

Re: How to speedup instances operations?

Post by TAO »

amazing, i did exactly the same by rebuilding indexes only once and just wanted to push it on github, i think it is done now and do not need to work on it anymore, thanks again.
daros
Posts: 280
Joined: Thu Dec 12, 2019 3:25 pm
Location: inside human language
Contact:

Re: How to speedup instances operations?

Post by daros »

Thanks a lot Dade and Tao, we are going to implement it immediately and let you know. Thanks again.
bartek_zgo
Posts: 116
Joined: Mon Oct 26, 2020 11:42 am

Re: How to speedup instances operations?

Post by bartek_zgo »

Thanks Dade and TAO. It is much better.
When I have 1 million instances it takes 1,2s to remove. That is very nice.
but....
If I have 350k instances of object A, 350k instances of object B and 350k instances of object C
- it takes 2minutes! to remove first one
- 50s to remove second one
- less than 1s to remove last one
What is more interesting. The order matters.
If I remove first A than B it takes much more than when I remove first B than A. I have added some logs to luxcore code and here is what I have found.

Code: Select all

[SDL][47.522] Deleting instances v5. count = 229079
[SDL][47.522] Light check
[SDL][47.621] Obj defs remove
[SDL][47.621]   Begin remove
[SDL][47.691]   Sort
[SDL][47.693]   Remove
[SDL][86.933]   Build idx start
[SDL][87.341]   Build ids end
[SDL][87.354] Add Action
[SDL][87.354] DONE

[SDL][87.757] Deleting instances v5. count = 229079
[SDL][87.758] Light check
[SDL][87.853] Obj defs remove
[SDL][87.853]   Begin remove
[SDL][87.934]   Sort
[SDL][87.936]   Remove
[SDL][107.317]  Build idx start
[SDL][107.541]  Build ids end
[SDL][107.559] Add Action
[SDL][107.559] DONE

[SDL][107.801] Deleting instances v5. count = 229079
[SDL][107.801] Light check
[SDL][107.883] Obj defs remove
[SDL][107.883]  Begin remove
[SDL][107.943]  Sort
[SDL][107.945]  Remove
[SDL][107.945]  Build idx start
[SDL][107.968]  Build ids end
[SDL][107.985] Add Action
[SDL][107.985] DONE

Code: Select all

void Scene::DeleteObjects(vector<string> &objNames) {

        SDL_LOG("Deleting instances v5. count = " << objNames.size() );

        SDL_LOG("Light check");
        // Delete the light sources
        BOOST_FOREACH(const string &objName, objNames) {
                if (objDefs.IsSceneObjectDefined(objName)) {
                        const SceneObject *oldObj = objDefs.GetSceneObject(objName);
                        const bool wasLightSource = oldObj->GetMaterial()->IsLightSource();

                        // Check if the old object was a light source
                        if (wasLightSource) {
                                editActions.AddActions(LIGHTS_EDIT | LIGHT_TYPES_EDIT);

                                // Delete all old triangle lights
                                const ExtMesh *mesh = oldObj->GetExtMesh();
                                const string prefix = Scene::EncodeTriangleLightNamePrefix(oldObj->GetName());
                                for (u_int i = 0; i < mesh->GetTotalTriangleCount(); ++i)
                                        lightDefs.DeleteLightSource(prefix + ToString(i));
                        }
                }
        }

        SDL_LOG("Obj defs remove");
        objDefs.DeleteSceneObjects(objNames);

        SDL_LOG("Add Action");
        editActions.AddAction(GEOMETRY_EDIT);
        SDL_LOG("DONE");
}


void NamedObjectVector::DeleteObjs(const vector<string> &names) {
        vector<u_int> removeList;
        removeList.reserve(names.size());
        SDL_LOG("\tBegin remove");
        for (const string &name : names) {
                if (IsObjDefined(name)) {
                        const u_int index = GetIndex(name);
                        removeList.push_back(index);
                }
        }
        SDL_LOG("\tSort");
        sort(removeList.begin(), removeList.end(), greater<u_int>());

        SDL_LOG("\tRemove");
        for (u_int i : removeList)
                objs.erase(objs.begin() + i);

        SDL_LOG("\tBuild idx start");
        // I have to rebuild the indices from scratch
        name2index.clear();
        index2obj.clear();

        for (u_int i = 0; i < objs.size(); ++i) {
                NamedObject *obj = objs[i];

                name2index.insert(Name2IndexType::value_type(obj->GetName(), i));
                index2obj.insert(Index2ObjType::value_type(i, obj));
        }
        SDL_LOG("\tBuild ids end");
}
User avatar
TAO
Developer
Developer
Posts: 850
Joined: Sun Mar 24, 2019 4:49 pm
Location: France
Contact:

Re: How to speedup instances operations?

Post by TAO »

Based on deleting the function source, all the slowness that you mention in the second test is coming from the order of deleting objects or in programming term order of the name vector that you send for deletion. for example, if you pup up the last item to the first item it will be fast but if you remove objects backward (from the end button of the vector) or even in random order it will be instantly slower.
The simple test you can do is to remove objects in a different order as I mention and you will see the difference.
By the way, I or dade may be able to improve it as you do some optimization in your side of code to improve the way of sending objects to delete function.
Post Reply