This is the mail archive of the systemtap@sourceware.org mailing list for the systemtap project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: array sorting checked in


On 9/23/05, Martin Hunt <hunt@redhat.com> wrote:
> I checked in several new functions to the runtime.
>
> _stp_map_sort(MAP map, int keynum, int dir)
> _stp_map_sortn(MAP map, int n, int keynum, int dir)
> _stp_map_printn(MAP map, int n, const char *fmt)
>
am I missing something?

I thought the idea of systemtap was to be fast, and unobtrusive?

yet you want to allow sorrting an array  of  unknown size using bubble
sort? that can be as bad as  O(n log n) quite possibly with a lock
held? if the array has 10,000 or 100,000 elements if you sort it even
once a second it will take its toll on the system and performance. The
programmer can' t know in advance the size of the array, if he knew
that information he wouldn't be running systemtap.

if you want to maintain stability and accuracy, you either have to
limit the size of the array and quite possibilty store it in order,
which is  O(1) operation for each addition.  and do it with minimal or
no locking, if you wish the system to scale in an SMP environment.

James Dickens
uadmin.blogspot.com


[snipped]


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]