Optimization question: Is there a way to compute only the "visible" portion of data for submission to ImGui?

[unpacklo]

Hi Omar,

I've been working on a small data packer tool with a GUI element to see the contents of the pack file. Our game currently has around ~12,000 files that need to be processed in some way and I show the contents of the pack file like so:

The overall layout of the window is very predictable and all data is indexed via simple array accesses.

Right now I just iterate over all the contents of the pack file and submit everything to ImGui. Obviously, with as many items in the pack file as I currently have, the performance is low. Is there some way for me to determine some bounds of the visible contents of the window and still scroll properly so I can keep high perf?

Thanks again, keep up the awesome work!

-Dale Kim

[ocornut]

If you are dealing with thousands of entries you probably want to perform clipping yourself, yes.
I just realised the functions are not all nicely exposed but at the moment as a workaround you can do:
EDIT Helper provided in next message.

// get scissor rectangle in screen space
ImVec4 clip_rect = ImGui::GetWindowDrawList()->clip_rect_stack.back()

// calculate vertical bounds in window space
ImGui2 window_pos = ImGui::GetWindowPos();
float y1 = clip_rect.y - window_pos.y;
float y2 = clip_rect.w - window_pos.y;

From there on

ImGui2 pos = ImGui::GetCursorPos();
float line_height = ImGui::GetTextLineHeight();
int lines_skipped = (int)((clip_rect.y - pos.y) / line_height) - 1;
pos.y += lines_skipped * line_height;
ImGui::SetCursorPos(pos);

// display your stuff from index "lines_skipped"
// until GetCursorPos().y < y2
// then do another SetCursorPos() to adjust the final cursor to take account of the clipped line

Let me know if that is confusing. I will look into simplifying this process with the right helpers (if you have any suggestion). Note that TextUnformatted() does something similar for you when you pass it large blurb of text.

However aside from the clipping the Columns API is currently unbearably slow, which is also something I ought to look into. But it shouldn't be a problem at this scale once you implement the clipping.

[ocornut]

I have added a helper function _CalcListClipping()_ to do that

// Helper to calculate clipping of large list of evenly sized items. 
// If you are displaying thousands of items and you have a random access to the list, you can perform clipping yourself to save on CPU.
// {
//    float item_height = ImGui::GetTextLineHeightWithSpacing();
//    int display_start, display_end;
//    ImGui::CalcListClipping(count, item_height, &display_start, &display_end);            // calculate how many to clip/display
//    ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (display_start) * item_height);         // advance cursor
//    for (int i = display_start; i < display_end; i++)                                     // display only visible items
//        // TODO: display visible item
//    ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (count - display_end) * item_height);   // advance cursor
// }
void ImGui::CalcListClipping(int items_count, float items_height, int* out_items_display_start, int* out_items_display_end);

Here's my test code

        if (ImGui::Begin("Clipping test"))
        {
            static bool use_clipping = false;
            static bool use_columns = false;
            ImGui::Checkbox("use_clipping", &use_clipping);
            ImGui::Checkbox("use_columns", &use_columns);
            ImGui::Separator();
            ImGui::BeginChild("##scrolling");
            float items_height = ImGui::GetTextLineHeightWithSpacing();
            int items_count = 12000;
            int display_start = 0, display_end = items_count;
            if (use_clipping)
                ImGui::CalcListClipping(items_count, items_height, &display_start, &display_end);
            ImGui::SetCursorPosY(ImGui::GetCursorPosY() + display_start * items_height);
            if (use_columns)
            {
                ImGui::Columns(4);
                for (int i = display_start; i < display_end; i++)
                {
                    ImGui::Text("/assets/dsfjkdsjkfs/sdjfjkdsfsfdsjfsjfjksfjskfjdsjfsjjjd/d/");
                    ImGui::NextColumn();
                    ImGui::Text("%d", 38487323);
                    ImGui::NextColumn();
                    ImGui::Text("%d", (i % 100)*123);
                    ImGui::NextColumn();
                    ImGui::Text("false");
                    ImGui::NextColumn();
                }
                ImGui::Columns(1);
            }
            else
            {
                for (int i = display_start; i < display_end; i++)
                    ImGui::Text("%05d: /assets/%05d/blahblahblah/d/", i, i);
            }
            ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (items_count - display_end) * items_height);
            ImGui::Text("");
            ImGui::EndChild();
        }
        ImGui::End();

With manual clipping the framerate gets back to the maximum I get in the test application with my drivers (~2000 fps on DX11 sample).

Adding UTF-8 support and other features still put a bit of a hit on performance for normal Text calls. They should be lighter when not manually clipped so I will work on that next.

[unpacklo]

Omar, this is excellent stuff!

I hooked it into my test program and things are looking great:

My current code for the above looks something like this:

ImGui::Text("AssetManifest contents:");
ImGui::Separator();
ImGui::BeginChild("##scrolling");
ImGui::Columns(4);

// Column header
ImGui::Text("Index");
ImGui::Separator();
ImGui::NextColumn();
ImGui::Text("Path");
ImGui::Separator();
ImGui::NextColumn();
ImGui::Text("Offset");
ImGui::Separator();
ImGui::NextColumn();
ImGui::Text("Bytes");
ImGui::Separator();
ImGui::NextColumn();

float itemHeight = ImGui::GetTextLineHeightWithSpacing();
int displayStart = 0, displayEnd = pack.manifest->numPaths;

ImGui::CalcListClipping(pack.manifest->numPaths, itemHeight, &displayStart, &displayEnd);
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (displayStart * itemHeight));

// Column contents
for (int i = displayStart; i < displayEnd; ++i)
{
    ImGui::Text("%d", i);
}

ImGui::NextColumn();
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (displayStart * itemHeight));

for (int i = displayStart; i < displayEnd; ++i)
{
    ImGui::Text("\"%s\"", pack.manifest->paths[i]);
}

ImGui::NextColumn();
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (displayStart * itemHeight));

for (int i = displayStart; i < displayEnd; ++i)
{
    ImGui::Text("%zu", pack.manifest->offsets[i]);
}

ImGui::NextColumn();
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (displayStart * itemHeight));

for (int i = displayStart; i < displayEnd; ++i)
{
    ImGui::Text("%zu", pack.manifest->bytes[i]);
}

ImGui::Columns(1);
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + ((pack.manifest->numPaths - displayEnd) * itemHeight));
ImGui::Text("END OF LISTING!");
ImGui::EndChild();

I know you mentioned in an issue I brought up before with the separators not respecting the column boundaries. Currently, I have to use multiple separators at the beginning with my "column header" section to ensure all the contents of each column align properly. No big deal here, but one of those little things to make sure it's just right.

The only real issue I encountered was how to get the clipping to work correctly if I wanted to have a column header section and write a column content loop like this:

ImGui::Text("AssetManifest contents:");
ImGui::Separator();
ImGui::BeginChild("##scrolling");
ImGui::Columns(4);

// Column header                                                                                                                                                                                                                                                                
ImGui::Text("Index");
ImGui::Separator();
ImGui::NextColumn();
ImGui::Text("Path");
ImGui::Separator();
ImGui::NextColumn();
ImGui::Text("Offset");
ImGui::Separator();
ImGui::NextColumn();
ImGui::Text("Bytes");
ImGui::Separator();
ImGui::NextColumn();

float itemHeight = ImGui::GetTextLineHeightWithSpacing();
int displayStart = 0, displayEnd = pack.manifest->numPaths;

ImGui::CalcListClipping(pack.manifest->numPaths, itemHeight, &displayStart, &displayEnd);
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (displayStart * itemHeight));

// Column contents                                                                                                                                                                                                                                                              
for (int i = displayStart; i < displayEnd; ++i)
{
    ImGui::Text("%d", i);
    ImGui::NextColumn();
    ImGui::Text("\"%s\"", pack.manifest->paths[i]);
    ImGui::NextColumn();
    ImGui::Text("%zu", pack.manifest->offsets[i]);
    ImGui::NextColumn();
    ImGui::Text("%zu", pack.manifest->bytes[i]);
    ImGui::NextColumn();
}

ImGui::Columns(1);
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + ((pack.manifest->numPaths - displayEnd) * itemHeight));
ImGui::Text("END OF LISTING!");
ImGui::EndChild();

Which yields results like this:

Notice the line starting with 10 which I can see, but the rest of the columns don't show their contents for that line.

-Dale Kim

[ocornut]

Moving discussion to another thread and closing this specific issue (Columns are a bunch of issues!)

"
Your second issue is because when we do the SetCursorPosY() we are already within the first column so we are making that cell very big. As we call NextColumn() the cursor resets itself to the "top". One workaround is to get out of columns first.

ImGui::Columns(1);
ImGui::CalcListClipping(items_count, items_height, &display_start, &display_end);
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + display_start * items_height);
ImGui::Columns(4);
"

[Flix01]

I've added a gist just to consolidate and generalize the code posted by Roflraging.
It's not very usable at the present state, but I'll probably improve it, if I have some time.

https://gist.github.com/Flix01/94b0bf3069476a1344ac

UPDATE: improved gist a bit adding basic cell text formatting, optional column reordering (programmatically) and row sorting by clicking on the column headers.

UPDATE 2: added (single) row selection support and cell editing support. I think I'll stop developing it for now: I've added all the features I needed.

[ocornut]

I'm not sure about that. It seems to defeat a lot of the ImGui design principles, storing and retaining thing prior to display. Notice how the original code is shorter than even your examples code - let alone the base classes you are using - and more flexible as well. So in my eyes it looks like an unnecessary abstraction to "consolidate" it that way.

I do agree that the Column API need improvements, we will probably end up implementing the features discussing above and simplify user's code so that headers can be declared with less code. We keep hammering the API to be more flexible more optimal more terse.

[Flix01]

Yes, I know. It's not my intention to integrate my gist into ImGui.

I just want to try to have more complete controls, without caring about the fact that they comply with the ImGui design principles or not.

[ocornut]

I went back to that from the different angle, which is that I want to make things faster even with zero clipping on user's side. So I looked at some of the primitives involved in the bottleneck and optimised them.

My test code displaying 12000 lines, 4 items and columns per line (so about 48000 submissions) went from 36.1 ms to 27.6 ms for an optimised build, and 288 ms to 195 ms for a non optimised build.

Of course it isn't a very meaningful scenario, since with the user's coarse clipping enabled time gets back to near 0.0 anyway. But this optimisation should benefit every part of ImGui.

[ocornut]

FYI i have added a higher level helper ImGuiListClipper to handle this pattern.

eb4ffd5

So this code above

int displayStart = 0, displayEnd = pack.manifest->numPaths;
ImGui::CalcListClipping(pack.manifest->numPaths, itemHeight, &displayStart, &displayEnd);
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + (displayStart * itemHeight));
for (int i = displayStart; i < displayEnd; ++i)
[...]
ImGui::SetCursorPosY(ImGui::GetCursorPosY() + ((pack.manifest->numPaths - displayEnd) * itemHeight));

Can become

ImGuiListClipper clipper(pack.manifest->numPaths, itemHeight);
for (int i = clipper.DisplayStart; i < clipper.DisplayEnd; ++i)
[...]
clipper.End();

CalcListClipping() is still available as the lower level function.