[SOLVED] Copy wxTreeCrtl from one tree to another

[dcbdbis]

Good Evening All,

I'm stuck. I don;t know if I've lost my creativity, or if I am pushing the limits of the wxTreeCtrl.

I have an app I'm developing for a client that lists inventory in a wxTreeCtrl, all of it categorized. I have a root, Cat, SubCatA, SubCatB, and Description. Four levels underneath the root. ~45,000 items of inventory.

The TreeCtrl works fine. BUT...To say that it's slow is an understatement, especially when I start using "AppendItem" for 41k's worth of description in the bottom level of the tree.

It takes 17 seconds to fully populate the tree- and I am on a AMD Threadripper Gen1 16 core w/64Gb of brains under the hood. Manjaro Linux. CodeBlocks 20.03 (built from source).

wxWidgets 3.1.3 also built from source (obvously)

I fear what my client's machine will do. I can't release it like this.

I thought I'd get cute and create in the main form, a pointer of type wxTreeCtrl, move my population code there, so I can load it once, then copy that tree into the ManageMaterials form (where the displayed tree resides), to prevent having to load it cleanly each time. I have gprof'd my code and valgrind' it. So I am assured that the AppendItem call X 41k times is what is hurting me. I've also used a wxStopWatch and played that game in various places in my code to do my own "poor man's" profilling. The results are the same. AppendItem is slow. InsertItem is no better.

I think my little pointer scheme would work....but I do not see a copy constructor, nor a member function to copy an entire tree from one tree to another in wxTreeCtrl.

I am asking for help to:

a) SpeedUp "AppendItem" (still slow when I replace it with "InsertItem").

or

b) Or a method to quickly copy an entire tree from one tree to another that doesn't take 17 seconds. I need to do it in one second or under. I know my customer (25+ years) - and he is impatient.

When this app was in C# under .NET before getting "orders" to port it.....I saved the tree to a file, then read it in from a file at next form load and it took under 0.25 seconds to repopulate a TreeView this way. I don't see a way to save a tree to disk in wxTreeView. I can extend the class - but parsing through the whole tree isn't going to help me at all - in fact it may make it worse.

I can't ask my user to wait 15-20 seconds each time they want to use their materials library......

My data source is SQLite, wrapped in a class I wrote that you will see in the example code below. And those calls are only costing me ~ 2-4ms.....And there are only four calls in the entire procedure - so it's not SQL.

Suggestions would be greatly appreciated....

I have attached one of my routines for one of the subcats for peer review, in case I'm doing something really stupid........

I'm old school before you criticize the code style. I cut my teeth on an old mainframe where you interfaced with it using green punch cards, and the response came back via a gigantic teletype terminal that shook the floor, where our interfaces were acoustically coupled @ 110 baud. Yeah - I'm old.

But this was the style we had to follow at Carrier before I retired and I like it, so I adopted it for my freelance work.

THANK YOU for taking the time to read this.....

Sincerely and respectfully,

Dave

[New Pagodi]

If I'm understanding correctly, you read from the database to some sort tree structure and then copy that structure to a tree control. If that's right, maybe you could use wxDataViewCtrl with a model designed to implement the virtual methods based on that tree structure you've built from the database.

[dcbdbis]

Here is a screencap of the populated tree...... (attached)


Dave

[New Pagodi]

If I'm understanding correctly, you read from the database to some sort tree structure and then copy that structure to a tree control. If that's right, maybe you could use wxDataViewCtrl with a model designed to implement the virtual methods based on that tree structure you've built from the database.

Here's a simple example showing this idea. It randomly generates a tree with 45000 items. I think it's reasonably fast.

Code: Select all

// For compilers that support precompilation, includes "wx/wx.h".
#include "wx/wxprec.h"

#ifdef __BORLANDC__
    #pragma hdrstop
#endif

// for all others, include the necessary headers (this file is usually all you
// need because it includes almost all "standard" wxWidgets headers)
#ifndef WX_PRECOMP
    #include "wx/wx.h"
#endif

#include <wx/dataview.h>
#include <random>
#include <queue>

// A simple tree class
class TreeNode
{
public:
    TreeNode(const wxString& );
    virtual ~TreeNode();
    TreeNode* Append(TreeNode*);

    TreeNode* GetParent() const {return m_parent;}
    TreeNode* GetFirstChild() const {return m_firstChild;}
    TreeNode* GetNextSibling() const {return m_nextSibling;}
    wxString GetLabel() const {return m_label;}

private:
    TreeNode* m_firstChild;
    TreeNode* m_nextSibling;
    TreeNode* m_parent;

    wxString m_label;
};

TreeNode::TreeNode(const wxString& label)
{
    m_firstChild = NULL;
    m_nextSibling = NULL;
    m_parent = NULL;

    m_label = label;
}

TreeNode::~TreeNode()
{
    TreeNode* nextNode;
    for ( TreeNode* n = m_firstChild; n != NULL;  )
    {
        nextNode = n->m_nextSibling;
        delete n;
        n = nextNode;
    }
}

TreeNode* TreeNode::Append(TreeNode* newChild)
{
    TreeNode* child = m_firstChild;

    if ( child == NULL )
    {
        m_firstChild = newChild;
    }
    else
    {
        while ( child->m_nextSibling != NULL )
        {
            child = child->m_nextSibling;
        }

        child->m_nextSibling = newChild;
    }

    newChild->m_parent = this;

    return newChild;
}

// A model for wxDataViewCtrl using the simple tree class
class MyTreeModel:public wxDataViewModel
{
public:
    MyTreeModel(TreeNode* t){m_tree = t;}
    ~MyTreeModel(){delete m_tree;}
    virtual unsigned int GetChildren(const wxDataViewItem&,
                                     wxDataViewItemArray&) const wxOVERRIDE;
    virtual unsigned int GetColumnCount() const  wxOVERRIDE;
    virtual wxString GetColumnType(unsigned int) const  wxOVERRIDE;
    virtual wxDataViewItem GetParent(const wxDataViewItem&) const wxOVERRIDE;
    virtual void GetValue(wxVariant&, const wxDataViewItem&,
                          unsigned int) const wxOVERRIDE;
    virtual bool IsContainer(const wxDataViewItem&) const wxOVERRIDE;
    virtual bool SetValue (const wxVariant&, const wxDataViewItem&,
                           unsigned int) wxOVERRIDE;
private:
    TreeNode* m_tree;
};


unsigned int MyTreeModel::GetChildren (const wxDataViewItem &item,
                                       wxDataViewItemArray& children) const
{
    unsigned int childCount = 0;
    TreeNode* curNode = NULL;

    if ( item.IsOk() )
    {
        curNode = reinterpret_cast<TreeNode*>(item.GetID());
    }
    else
    {
        curNode = m_tree;
    }

    for ( TreeNode* n = curNode->GetFirstChild() ; n != NULL ;
          n = n->GetNextSibling())
    {
        ++childCount;
        wxDataViewItem newItem(n);
        children.Add(newItem);
    }

    return childCount;
}

unsigned int MyTreeModel::GetColumnCount () const
{
    return 1;
}

wxString MyTreeModel::GetColumnType (unsigned int col) const
{
    return "string";
}

wxDataViewItem MyTreeModel::GetParent(const wxDataViewItem& item) const
{
    if ( item.IsOk() )
    {
        TreeNode* node = reinterpret_cast<TreeNode*>(item.GetID());
        TreeNode* par = node->GetParent();

        if ( par == m_tree )
        {
             return wxDataViewItem(NULL);
        }
        else
        {
            return wxDataViewItem(par);
        }
    }
    else
    {
        return wxDataViewItem(NULL);
    }
}

void MyTreeModel::GetValue(wxVariant& variant, const wxDataViewItem& item,
                           unsigned int col) const
{
    if ( item.IsOk() )
    {
        void* d = item.GetID();
        TreeNode* n = reinterpret_cast<TreeNode*>(d);

        variant = n->GetLabel();
    }
}

bool MyTreeModel::IsContainer(const wxDataViewItem& item) const
{
    if ( item.IsOk() )
    {
        void* d = item.GetID();
        TreeNode* n = reinterpret_cast<TreeNode*>(d);

        return n->GetFirstChild() != NULL;
    }
    else
    {
        return true;
    }
}

bool MyTreeModel::SetValue (const wxVariant& variant,
                            const wxDataViewItem& item, unsigned int col)
{
    return true;
}


class MyFrame : public wxFrame
{
    public:
        MyFrame(wxWindow* parent, int id = wxID_ANY, wxString title = "Demo",
                wxPoint pos = wxDefaultPosition, wxSize size = wxDefaultSize,
                int style = wxDEFAULT_FRAME_STYLE|wxTAB_TRAVERSAL );
};


MyFrame::MyFrame(wxWindow* parent, int id, wxString title, wxPoint pos,
                 wxSize size, int style )
        :wxFrame(parent, id, title, pos, size, style )
{
    wxDataViewCtrl* dvc = new wxDataViewCtrl(this, wxID_ANY, wxDefaultPosition,
                                             wxDefaultSize, wxDV_NO_HEADER);

    // Build a random tree where each node has between 2 and 40 children.
    std::random_device rd; // obtain a random number from hardware
    std::mt19937 eng(rd()); // seed the generator
    std::uniform_int_distribution<> distr(2, 40); // define the range

    TreeNode* root = new TreeNode("");
    std::queue<TreeNode*> nodes;
    const int nodesToGenerate = 45000;
    int curNodeCount = 0;

    nodes.push(root);

    while ( curNodeCount < nodesToGenerate && !nodes.empty() )
    {
        int totalChildren = distr(eng);
        TreeNode* n = nodes.front();
        nodes.pop();

        wxString base = n->GetLabel();
        if ( base.IsEmpty() )
        {
            base = "Item ";
        }

        for (int i = 1 ; i <= totalChildren ; ++i )
        {
            wxString label = wxString::Format("%s-%02d",base,i);
            nodes.push(n->Append(new TreeNode(label)));
            ++curNodeCount;
        }
    }

    // Create a model using this tree and assign the model to dvc.
    MyTreeModel* model = new MyTreeModel(root);
    dvc->AppendTextColumn("",0);
    dvc->AssociateModel(model);
    model->DecRef();  // avoid memory leak !!
}


class MyApp : public wxApp
{
    public:
        virtual bool OnInit()
        {
            MyFrame* frame = new MyFrame(NULL);
            frame->Show();
            return true;
        }
};

wxIMPLEMENT_APP(MyApp);

edit: fixed a bug in the GetParent method.

[dcbdbis]

Thank You @ New Pagodi,


I'll take a look at the code in the Am. My old brain cells are fried at the moment......

THANK YOU for the assistance. I appreciate it....


Dave

[dcbdbis]

Good Evening All,


THANK YOU for the code to @New Pagodi.

I copy-n-pasted it into mousepad....and it gave me some ideas. Perhaps a blend of your techniques and my ideas.

I'll report back once I have a solution in place and mark the thread solved once I have a solution - and of course I'll post the finished solution for all..


THANK YOU!


Dave

[dcbdbis]

Currently I'm taking what I received from this thread, and marrying it with a separate thread of execution that starts at program startup, and will finish before the user can get to the affected section. I'll keep all posted on progress once I find a solve.


Dave

[doublemax]

As you're only allowed to access GUI elements from the main thread, i think you'll run into a dead end with using multiple threads for populating the wxTreeCtrl. Try looking into wxDataViewCtrl with a custom wxDataViewModel that takes the data directly from the database.

[dcbdbis]

@doublemax....


I had forgotten about that...GUI access in threads was problematic way back when I was still in the workforce formally - and younger.

THANK YOU for the reminder of the known pitfall that I wasn't remembering.


Dave

[dcbdbis]

Well - I have spent the majority of today playing with wxStopWatch in various sections of my code.... The CPP profiler is not granular enough for me to see which line(s) are causing the slowdown....And it is NOT wxTreeCtrl that is slow. 44K items in 117 ms. That's actually screaming fast.

And with egg on my face------It is NOT the wxTreeCtrl that is slow, it's the SQL queries that I do in the while loop.

So I need to redesign my SQL queries to be one time only - outside of the iterative loop, then parsing from there in some manner that doesn't isn't slow. This I can do.

I THANK EVERYONE for their support. I sincerely appreciate it.


FYI,


Dave

[ONEEYEMAN]

Hi,
Do you have any indexes created?
If yes - maybe they are wrong and actually slowing the the queries instead.

Thank you.

[dcbdbis]

No indexes at this point....Nor multiple openings and closings of the database either. Open - read a bunch - then close.

I am convinced that it's the manner in which I am using SQLite causing the issues....So at the moment, I'm moving things around, and then putting things in a data-structure from SQL, then working with the datastructure for speed.

The code isn't in finished form - yet....- but the initial results are looking good.


Dave

[dcbdbis]

@OneEyeMan,

THANK YOU for the post. You were exactly on point. Indexes - actually the lack of indexes. I forgot to create them at DB creation time...and I created three separate index for my specific needs and the issue is resolved. I had no idea that index could speed up the process that much!

I am not an SQL guy.....But after I created the indexes I needed....the operational time went down to ~.5 seconds. PERFECT!

Everyone has been very helpful and patient.

I APPRECIATE IT!


Dave