This is the mail archive of the
systemtap@sourceware.org
mailing list for the systemtap project.
Re: array sorting checked in
- From: James Dickens <jamesd dot wi at gmail dot com>
- To: Martin Hunt <hunt at redhat dot com>
- Cc: systemtap at sources dot redhat dot com
- Date: Sat, 24 Sep 2005 00:25:19 -0600
- Subject: Re: array sorting checked in
- Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=AV1OS/fPokPgisvFK8KfjoGGHjwM5Vq31fTuzOXhn0KkSCy9Bo8gHXgVY08v5s9F0flc9wQ0+ncqUcTt0u+pC46LwzrzseaT1p3AkDITqpCml3ptAx2kTUhT0lUWFtm4mV/QBGeBXKe7tU+dVJ6rN1SKhvNcotjbGi6ArCwsbqY=
- References: <1127464449.7927.10.camel@dragon>
- Reply-to: James Dickens <jamesd dot wi at gmail dot com>
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]