Opened 4 years ago
#16100 new bug
BColumnListView: AddRow and RemoveRow have O(n) time complexity
| Reported by: | X512 | Owned by: | nobody |
|---|---|---|---|
| Priority: | normal | Milestone: | Unscheduled |
| Component: | Kits/Interface Kit | Version: | R1/Development |
| Keywords: | Cc: | ||
| Blocked By: | Blocking: | ||
| Platform: | All |
Description
This is hrev54241.
BColumnListView changing have O(n) complexity that lead to O(n2) complexity for whole table updating. Problem is in OutlineView::FindRect that is called on each insert and delete and it traverse whole list. It should be possible to have fixed height rows and O(1) FindRect complexity.
profile -f output:
hits in us in % image function
------------------------------------------------------------------------------
795 795000 100.00 219291 runtime_loader
795 795000 100.00 219290 commpage_thread_exit
793 793000 99.75 219292 _start
793 793000 99.75 219292 main
792 792000 99.62 219294 BApplication::DispatchMessage(BMessage*, BHandler*)
792 792000 99.62 219294 BApplication::Run()
792 792000 99.62 219294 BLooper::Loop()
792 792000 99.62 219294 BLooper::task_looper()
792 792000 99.62 219292 ServicesApplication::ReadyToRun()
792 792000 99.62 219292 ListHandles(BColumnListView*, BRow*)
565 565000 71.07 219292 BPrivate::OutlineView::FindRect(BRow const*, BRect*)
513 513000 64.53 219292 BColumnListView::InvalidateRow(BRow*)
513 513000 64.53 219292 BRow::SetField(BField*, int)
322 322000 40.50 219294 BList::ItemAt(int) const
268 268000 33.71 219292 BPrivate::OutlineView::AddRow(BRow*, int, BRow*)
191 191000 24.03 219292 BPrivate::RecursiveOutlineIterator::GoToNext()
67 67000 8.43 219292 BPrivate::RecursiveOutlineIterator::CurrentRow() const
65 65000 8.18 219292 BRow::Height() const
46 46000 5.79 219294 BList::CountItems() const
4 4000 0.50 219294 BString::SetToFormat(char const*, ...)
4 4000 0.50 219294 BString::SetToFormatVarArgs(char const*, __va_list_tag*)
4 4000 0.50 219296 malloc
4 4000 0.50 219296 BPrivate::threadHeap::malloc(unsigned long)
3 3000 0.38 219293 operator new(unsigned long)
3 3000 0.38 219296 _IO_vfprintf
2 2000 0.25 219296 _IO_vsnprintf
2 2000 0.25 219294 __initialize_locale_kit()
2 2000 0.25 219291 load_program
2 2000 0.25 219294 BLocaleRoster::BLocaleRoster()
2 2000 0.25 219296 BPrivate::hoardHeap::findAvailableSuperblock(int, BPrivate::block*&, BPrivate::processHeap*)
2 2000 0.25 219296 pthread_once
2 2000 0.25 219291 init_dependencies(image_t*, bool) [clone .constprop.8]
2 2000 0.25 219294 BPrivate::InitializeLocaleRoster()
2 2000 0.25 219294 BPrivate::MutableLocaleRoster::MutableLocaleRoster()
2 2000 0.25 219294 initialize_after
2 2000 0.25 219294 BPrivate::MutableLocaleRoster::Default()
1 1000 0.13 219296 __mutex_lock
1 1000 0.13 219298 icu_57::ZoneMeta::getCanonicalCLDRID(icu_57::UnicodeString const&, UErrorCode&) [clone .part.8]
1 1000 0.13 219294 BList::BList(int)
1 1000 0.13 219294 BList::_ResizeArray(int)
1 1000 0.13 219294 BTimeZone::SetTo(char const*, BLanguage const*)
1 1000 0.13 219296 _kern_write_port_etc
1 1000 0.13 219296 tls_address
1 1000 0.13 219296 _IO_default_xsputn
1 1000 0.13 219298 icu_57::OlsonTimeZone::OlsonTimeZone(UResourceBundle const*, UResourceBundle const*, icu_57::UnicodeString const&, UErrorCode&)
1 1000 0.13 219298 icu_57::TimeZone::createTimeZone(icu_57::UnicodeString const&)
1 1000 0.13 219296 BPrivate::superblock::superblock(int, int, BPrivate::hoardHeap*)
1 1000 0.13 219296 BPrivate::superblock::makeSuperblock(int, BPrivate::processHeap*)
1 1000 0.13 219303 ustr_hashUCharsN_57
1 1000 0.13 219298 icu_57::(anonymous namespace)::createSystemTimeZone(icu_57::UnicodeString const&, UErrorCode&)
1 1000 0.13 219294 BMessenger::BMessenger(char const*, int, int*)
1 1000 0.13 219292 BPrivate::OutlineView::FixScrollBar(bool)
1 1000 0.13 219292 BRow::BRow()
1 1000 0.13 219293 operator new(unsigned long, std::nothrow_t const&)
1 1000 0.13 219294 BApplication::BApplication(char const*)
1 1000 0.13 219294 BApplication::_InitData(char const*, bool, int*)
1 1000 0.13 219294 BApplication::_InitGUIContext()
1 1000 0.13 219294 BApplication::_ConnectToServer()
1 1000 0.13 219294 BPrivate::create_desktop_connection(BPrivate::ServerLink*, char const*, int)
1 1000 0.13 219294 BLaunchRoster::GetData(char const*, BMessage&)
1 1000 0.13 219294 BLaunchRoster::_SendRequest(BMessage&, BMessage&)
1 1000 0.13 219294 BMessage::_SendMessage(int, int, int, BMessage*, long, long) const
1 1000 0.13 219294 BTimeZone::BTimeZone(char const*, BLanguage const*)
1 1000 0.13 219294 BMessenger::SendMessage(BMessage*, BMessage*, long, long) const
1 1000 0.13 219294 BMessenger::_InitData(char const*, int, int*)
1 1000 0.13 219294 BMessage::Private::SendMessage(int, int, int, BMessage*, long, long) const
1 1000 0.13 219294 BScrollBar::SetRange(float, float)
1 1000 0.13 219294 BScrollBar::_DoubleArrows() const
1 1000 0.13 219294 BScrollBar::_UpdateThumbFrame()
1 1000 0.13 219294 BView::Bounds() const
1 1000 0.13 219294 BPrivate::LocaleRosterData::LocaleRosterData(BLanguage const&, BFormattingConventions const&)
1 1000 0.13 219294 BPrivate::LocaleRosterData::Refresh()
1 1000 0.13 219294 BPrivate::LocaleRosterData::_Initialize()
1 1000 0.13 219294 BPrivate::LocaleRosterData::_LoadTimeSettings()
Note:
See TracTickets
for help on using tickets.
