On Monday, November 24, 2014 11:42:31 PM UTC-8, Uli wrote: > > >>> The Lee-Man <[email protected] <javascript:>> schrieb am 24.11.2014 > um 18:04 in > Nachricht <[email protected] > <javascript:>>: > [...] > > Here's the problem: the submitted patch makes this > > particular use case O(1). You can't get much faster > > Are you sure? You modified the compare function used by sort. Even if the > list is sorted before you add a new entry at the end, more tan one call to > the compare function is performed (unless I miss the obvious). Typically > the best you can get is like O(log2(n)) (for binary search) >
Yes. As I said, the sort is a non-issue, based on (1) the small amount of time it takes to sort a list, which is swamped by the amount of time it takes to do /sysfs I/O. So even though the search *does* (as you say) take longer than O(1), it never killed the CPU. > > > than that, i.e. it takes a fixed time no matter how > > many sessions are present. > > > > The only patches I can come up with make that > > search take O(n). That's because the only > > If you search for the extreme value of an unsorted list with n elements, > you can't beat that. That's why you (build and) sort the list if it's > intended to be searched more than once, I guess. > Yes, I can beat that, and the patch does just that. O(1) is better than O(n). When I tried to improve the patch that kept being the bottom line. No matter how much I optimize a search of the list, it's still going to have to search half the list (linearly), on average, before it finds the session being searched for. > > > way other than caching to find the "last session > > used" is to search through the session list. > > > [...] > > > -- You received this message because you are subscribed to the Google Groups "open-iscsi" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/open-iscsi. For more options, visit https://groups.google.com/d/optout.
