millisecond scheduler and CPU usage

Hello,

Trying to make a real-time scheduler to deal with musical (MIDI) sequencing,
I encounter this problem :

Basically, my goal is to build a scheduler with a precision of millisecond.
Here is two simple test versions of the loop to explain the problem (the
test run for 5 seconds) :

1) first, I tried with a timeout of 0.001 second :

(defvar *countIterations* 0)

(defun run ()
  (loop with delta = (get-internal-real-time)
        do 
        (mp:process-wait-with-timeout "" 0.001)
        (let ((ms (- (get-internal-real-time) delta)))
          (incf *countIterations*)
          (when (>= ms 5000)
            (return)
          ))))

(defun startChrono ()
    (setf *countIterations* 0)
    (mp:process-run-function "Chrono" nil #'run))

#|
RUN =>
(startChrono)
RESULT (after 5 seconds) =>
(values *countIterations*)
|#

Here I get something like 100 steps by second (*countIterations* is ± 530)
when I need 1000... (In fact, with a timeout of 0.01 or 0.001 the result is
practically the same)

2) Secondly, I tried with a timeout less than 0.001 second : suddenly, the
accuracy becomes really higher but the consumption of CPU resource becomes
also very high... (note that the result will be exactly the same with a
timeout of 0.00099 or with a timeout of 0.0001).

(defvar *countMS* 0)
(defvar *bag* nil)

(defun run ()
    (loop with delta = (get-internal-real-time)
          with prev = 0
          do (mp:process-wait-with-timeout "" 0.00099)
          (let* ((ms (- (get-internal-real-time) delta))
                 (interval (- ms prev)))
            (incf *countIterations*)
            (when (> interval 0)
              (setf prev ms)
              (incf *countMS*)
              (when (> interval 1) (push interval *bag*))
              (when (>= ms 5000) (return) ) ) )))

(defun startChrono ()
    (setf *countMS* 0 *countIterations* 0 *bag* nil)
    (mp:process-run-function "Chrono" nil #'run))
#|
RUN =>
(startChrono)
RESULT (after 5 seconds) =>
(values *countIterations* *countMS* (reverse *bag*))
|#

Here the *countIterations* is ± 146.000 (almost 30 iterations for a
millisecond) and the *countMS* is ± 4980. Witch means that the millisecond
resolution is perfectly correct for more than 99.5% of the time (this is
acceptable for what I have to do with).
In the *bag* variable you can observe the granularity : the most significant
interval is often at the start of the loop (something like 10 or 15 ms),
after that, the granularity stays in a very acceptable range (most of the
time less than 5ms).

****
 
The codes I run with a version derived of this loop give me a very good
result. Even when the scheduler is running and has a lot of tasks to do, I
can make real-time manipulation of the running sequence, interaction with
the CAPI interfaces and menu, generally without serious alteration of the
scheduler regularity.

The only problem is the consumption of CPU resources : For an Intel Imac
dual-core of 1.8 Ghz, something like 30 a 40% of the CPU for the user and ±
50% for the system (as you can see in the Mac activity monitor), just for
the loop running without any task...

There is something I misunderstand : Why do a simple loop like this consume
so many resources ? Is there any solution to limit the CPU usage ? Because
the timeout seems not to be the solution, witch other parameter may I adjust
?

Any advice greatly appreciated. Thanks !


Denis


       
        

-------------------------------------------------------
Denis Pousseur
70 rue de Wansijn
1180 Bruxelles, Belgique

Tel : 32 (0)2 219 31 09
Mail :  denis.pousseur@compositeurs.be
Website : http://compositeurs.be/Pousseur
-------------------------------------------------------

Re: millisecond scheduler and CPU usage

Hi Denis,

I assume, that you run your tests as a process with priority within  
normal scheduling range - not RTPRIO - so your process is subject to  
normal scheduling under the OS (with the resolution somewhere around  
10ms). On the other hand running app as RTPRIO might cause your  
system stop to respond to other events. I would say, that best  
solution for handling such jobs is to write kernel driver for the  
MIDI device

regards
Chris

On Jan 5, 2007, at 1:56 PM, Denis Pousseur wrote:

>
> Hello,
>
> Trying to make a real-time scheduler to deal with musical (MIDI)  
> sequencing,
> I encounter this problem :
>
> Basically, my goal is to build a scheduler with a precision of  
> millisecond.
> Here is two simple test versions of the loop to explain the problem  
> (the
> test run for 5 seconds) :
>
> 1) first, I tried with a timeout of 0.001 second :
>
> (defvar *countIterations* 0)
>
> (defun run ()
>   (loop with delta = (get-internal-real-time)
>         do
>         (mp:process-wait-with-timeout "" 0.001)
>         (let ((ms (- (get-internal-real-time) delta)))
>           (incf *countIterations*)
>           (when (>= ms 5000)
>             (return)
>           ))))
>
> (defun startChrono ()
>     (setf *countIterations* 0)
>     (mp:process-run-function "Chrono" nil #'run))
>
> #|
> RUN =>
> (startChrono)
> RESULT (after 5 seconds) =>
> (values *countIterations*)
> |#
>
> Here I get something like 100 steps by second (*countIterations* is  
> ± 530)
> when I need 1000... (In fact, with a timeout of 0.01 or 0.001 the  
> result is
> practically the same)
>
> 2) Secondly, I tried with a timeout less than 0.001 second :  
> suddenly, the
> accuracy becomes really higher but the consumption of CPU resource  
> becomes
> also very high... (note that the result will be exactly the same  
> with a
> timeout of 0.00099 or with a timeout of 0.0001).
>
> (defvar *countMS* 0)
> (defvar *bag* nil)
>
> (defun run ()
>     (loop with delta = (get-internal-real-time)
>           with prev = 0
>           do (mp:process-wait-with-timeout "" 0.00099)
>           (let* ((ms (- (get-internal-real-time) delta))
>                  (interval (- ms prev)))
>             (incf *countIterations*)
>             (when (> interval 0)
>               (setf prev ms)
>               (incf *countMS*)
>               (when (> interval 1) (push interval *bag*))
>               (when (>= ms 5000) (return) ) ) )))
>
> (defun startChrono ()
>     (setf *countMS* 0 *countIterations* 0 *bag* nil)
>     (mp:process-run-function "Chrono" nil #'run))
> #|
> RUN =>
> (startChrono)
> RESULT (after 5 seconds) =>
> (values *countIterations* *countMS* (reverse *bag*))
> |#
>
> Here the *countIterations* is ± 146.000 (almost 30 iterations for a
> millisecond) and the *countMS* is ± 4980. Witch means that the  
> millisecond
> resolution is perfectly correct for more than 99.5% of the time  
> (this is
> acceptable for what I have to do with).
> In the *bag* variable you can observe the granularity : the most  
> significant
> interval is often at the start of the loop (something like 10 or 15  
> ms),
> after that, the granularity stays in a very acceptable range (most  
> of the
> time less than 5ms).
>
> ****
>
> The codes I run with a version derived of this loop give me a very  
> good
> result. Even when the scheduler is running and has a lot of tasks  
> to do, I
> can make real-time manipulation of the running sequence,  
> interaction with
> the CAPI interfaces and menu, generally without serious alteration  
> of the
> scheduler regularity.
>
> The only problem is the consumption of CPU resources : For an Intel  
> Imac
> dual-core of 1.8 Ghz, something like 30 a 40% of the CPU for the  
> user and ±
> 50% for the system (as you can see in the Mac activity monitor),  
> just for
> the loop running without any task...
>
> There is something I misunderstand : Why do a simple loop like this  
> consume
> so many resources ? Is there any solution to limit the CPU usage ?  
> Because
> the timeout seems not to be the solution, witch other parameter may  
> I adjust
> ?
>
> Any advice greatly appreciated. Thanks !
>
>
> Denis
>
>
>
>
>
> -------------------------------------------------------
> Denis Pousseur
> 70 rue de Wansijn
> 1180 Bruxelles, Belgique
>
> Tel : 32 (0)2 219 31 09
> Mail :  denis.pousseur@compositeurs.be
> Website : http://compositeurs.be/Pousseur
> -------------------------------------------------------
>
>
>
>
>
>

Re: millisecond scheduler and CPU usage

Hi Chris,

Thanks for your answer. I've no idea how to run a process as RTPRIO... But
every tests I did with priorities don't change significantly the results I
got. In the example 1, even with the highest priority, the resolution stays
- as you say - around 10ms.

But when I set the timeout to a interval less than 1ms (example 2), it seems
that a very important change occurs in the way the OS deal with my process.
But how exactly, it's a mystery... Do you thing that there is something to
do with RTPRIO ? Is it a way to check this ?

Regards

Denis


Le 5/01/07 15:25, « [NOM] » <[ADRESSE]> a écrit :

> 
> Hi Denis,
> 
> I assume, that you run your tests as a process with priority within
> normal scheduling range - not RTPRIO - so your process is subject to
> normal scheduling under the OS (with the resolution somewhere around
> 10ms). On the other hand running app as RTPRIO might cause your
> system stop to respond to other events. I would say, that best
> solution for handling such jobs is to write kernel driver for the
> MIDI device
> 
> regards
> Chris
> 
> On Jan 5, 2007, at 1:56 PM, Denis Pousseur wrote:
> 
>> 
>> Hello,
>> 
>> Trying to make a real-time scheduler to deal with musical (MIDI)
>> sequencing,
>> I encounter this problem :
>> 
>> Basically, my goal is to build a scheduler with a precision of
>> millisecond.
>> Here is two simple test versions of the loop to explain the problem
>> (the
>> test run for 5 seconds) :
>> 
>> 1) first, I tried with a timeout of 0.001 second :
>> 
>> (defvar *countIterations* 0)
>> 
>> (defun run ()
>>   (loop with delta = (get-internal-real-time)
>>         do
>>         (mp:process-wait-with-timeout "" 0.001)
>>         (let ((ms (- (get-internal-real-time) delta)))
>>           (incf *countIterations*)
>>           (when (>= ms 5000)
>>             (return)
>>           ))))
>> 
>> (defun startChrono ()
>>     (setf *countIterations* 0)
>>     (mp:process-run-function "Chrono" nil #'run))
>> 
>> #|
>> RUN =>
>> (startChrono)
>> RESULT (after 5 seconds) =>
>> (values *countIterations*)
>> |#
>> 
>> Here I get something like 100 steps by second (*countIterations* is
>> ± 530)
>> when I need 1000... (In fact, with a timeout of 0.01 or 0.001 the
>> result is
>> practically the same)
>> 
>> 2) Secondly, I tried with a timeout less than 0.001 second :
>> suddenly, the
>> accuracy becomes really higher but the consumption of CPU resource
>> becomes
>> also very high... (note that the result will be exactly the same
>> with a
>> timeout of 0.00099 or with a timeout of 0.0001).
>> 
>> (defvar *countMS* 0)
>> (defvar *bag* nil)
>> 
>> (defun run ()
>>     (loop with delta = (get-internal-real-time)
>>           with prev = 0
>>           do (mp:process-wait-with-timeout "" 0.00099)
>>           (let* ((ms (- (get-internal-real-time) delta))
>>                  (interval (- ms prev)))
>>             (incf *countIterations*)
>>             (when (> interval 0)
>>               (setf prev ms)
>>               (incf *countMS*)
>>               (when (> interval 1) (push interval *bag*))
>>               (when (>= ms 5000) (return) ) ) )))
>> 
>> (defun startChrono ()
>>     (setf *countMS* 0 *countIterations* 0 *bag* nil)
>>     (mp:process-run-function "Chrono" nil #'run))
>> #|
>> RUN =>
>> (startChrono)
>> RESULT (after 5 seconds) =>
>> (values *countIterations* *countMS* (reverse *bag*))
>> |#
>> 
>> Here the *countIterations* is ± 146.000 (almost 30 iterations for a
>> millisecond) and the *countMS* is ± 4980. Witch means that the
>> millisecond
>> resolution is perfectly correct for more than 99.5% of the time
>> (this is
>> acceptable for what I have to do with).
>> In the *bag* variable you can observe the granularity : the most
>> significant
>> interval is often at the start of the loop (something like 10 or 15
>> ms),
>> after that, the granularity stays in a very acceptable range (most
>> of the
>> time less than 5ms).
>> 
>> ****
>> 
>> The codes I run with a version derived of this loop give me a very
>> good
>> result. Even when the scheduler is running and has a lot of tasks
>> to do, I
>> can make real-time manipulation of the running sequence,
>> interaction with
>> the CAPI interfaces and menu, generally without serious alteration
>> of the
>> scheduler regularity.
>> 
>> The only problem is the consumption of CPU resources : For an Intel
>> Imac
>> dual-core of 1.8 Ghz, something like 30 a 40% of the CPU for the
>> user and ±
>> 50% for the system (as you can see in the Mac activity monitor),
>> just for
>> the loop running without any task...
>> 
>> There is something I misunderstand : Why do a simple loop like this
>> consume
>> so many resources ? Is there any solution to limit the CPU usage ?
>> Because
>> the timeout seems not to be the solution, witch other parameter may
>> I adjust
>> ?
>> 
>> Any advice greatly appreciated. Thanks !
>> 
>> 
>> Denis
>> 
>> 
>> 
>> 
>> 
>> -------------------------------------------------------
>> Denis Pousseur
>> 70 rue de Wansijn
>> 1180 Bruxelles, Belgique
>> 
>> Tel : 32 (0)2 219 31 09
>> Mail :  denis.pousseur@compositeurs.be
>> Website : http://compositeurs.be/Pousseur
>> -------------------------------------------------------
>> 
>> 
>> 
>> 
>> 
>> 
> 
> 
> 
> 
> 



-------------------------------------------------------
Denis Pousseur
70 rue de Wansijn
1180 Bruxelles, Belgique

Tel : 32 (0)2 219 31 09
Mail :  denis.pousseur@compositeurs.be
Website : http://compositeurs.be/Pousseur
-------------------------------------------------------

Re: millisecond scheduler and CPU usage

--- Denis Pousseur <denis.pousseur@compositeurs.be> wrote:

> 
> Hi Chris,
> 
> Thanks for your answer. I've no idea how to run a process as RTPRIO... But
> every tests I did with priorities don't change significantly the results I
> got. In the example 1, even with the highest priority, the resolution stays
> - as you say - around 10ms.
> 
> But when I set the timeout to a interval less than 1ms (example 2), it
> seems
> that a very important change occurs in the way the OS deal with my process.
> But how exactly, it's a mystery... Do you thing that there is something to
> do with RTPRIO ? Is it a way to check this ?
> 
> Regards
> 
> Denis

Hi Denis,

The problem is that there are at least four timers in PC hardware. See
http://www.microsoft.com/whdc/system/CEC/mm-timer.mspx for a discussion of
the issues. Under Windows, the High Performance Event Timer (HPET), is used
for accurate sub-millisecond timing events.

>From your results, it appears that Lispworks is using the default
millisecond-and-above timer, which doesn't have good resolution, until you
specify sub-millisecond timings. Lispworks then appears to shift to a
different method for producing the events. I've used HPET calls under
Windows, under their former guise as MM (Multimedia) timer calls, and I don't
recall them introducing the OS and CPU overheads you've observed.

You may try finding the corresponding high-precision timing calls on each
platform you use and make OS-specific FFI calls from your code. I don't know
if that will cause any undesired interactions with Lispworks code, are you
using native threads in your version of Lispworks, and is the Lispworks
threading model robust enough that problems won't result? I don't know but it
may work out OK. Perhaps you could make the HPET calls in a native C thread
and perform Lispworks callbacks from there.

Alternatively, perhaps Lispworks may be persuaded to change their code to use
HPET equivs, at least on the platforms you need, if they are not doing so
now.

Jeff Caldwell

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com

Re: millisecond scheduler and CPU usage

I just realized what the 2002 article at
http://www.microsoft.com/whdc/system/CEC/mm-timer.mspx is really saying. The
older MM calls I was using use a combination of the four existing PC timers.
Intel has introduced / is introducing a new HPET hardware timer. Without the
new hardware timer, the article states that "Microsoft tests have found that,
while lowering the timer tick frequency to 2 milliseconds has a negligible
effect on system performance, a timer tick frequency of less than 2
milliseconds can significantly degrade overall system performance." 

>From that, it looks like Lispworks is doing what it should, that trying
things from C won't improve anything.

Jeff Caldwell


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com

Re: millisecond scheduler and CPU usage

Hi Jeff,

All this explanations are very interesting.

My approach, consisting of starting with a millisecond clock resolution, is
maybe a bad idea... In fact I have to schedule two kind of events : regular
events (for drawing counters and cursors) witch can really be scheduled at a
1/100sec resolution and episodic events witch need to be scheduled at a ms
resolution (musical events). So, I can maybe imagine a clock with a variable
resolution, 1/100 generally, 1/1000 when really needed. For instance when
the next event is at less than 15 (or 20) ms the resolution can turns to the
high resolution and otherwise return to normal resolution. There could be a
big advantage to this approach : the consumption of CPU resource would
become relative to the density of the events in the sequence (witch seems a
logical behavior...). After some tests in that way, it seems that I can
reduce the CPU resource needed by 4 or 5 for "normal" situation.

Anyway, it could be interesting to know from LW what's happening exactly
when setting a timeout under one millisecond... Indeed, I have no guarantee
that the undocumented actual behavior will be the same in future release....

Thanks for your help !

Best

Denis


Le 5/01/07 19:49, « [NOM] » <[ADRESSE]> a écrit :

> 
> I just realized what the 2002 article at
> http://www.microsoft.com/whdc/system/CEC/mm-timer.mspx is really saying.. The
> older MM calls I was using use a combination of the four existing PC timers.
> Intel has introduced / is introducing a new HPET hardware timer. Without the
> new hardware timer, the article states that "Microsoft tests have found that,
> while lowering the timer tick frequency to 2 milliseconds has a negligible
> effect on system performance, a timer tick frequency of less than 2
> milliseconds can significantly degrade overall system performance."
> 
>> From that, it looks like Lispworks is doing what it should, that trying
> things from C won't improve anything.
> 
> Jeff Caldwell
> 
> 
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
> 
> 



-------------------------------------------------------
Denis Pousseur
70 rue de Wansijn
1180 Bruxelles, Belgique

Tel : 32 (0)2 219 31 09
Mail :  denis.pousseur@compositeurs.be
Website : http://compositeurs.be/Pousseur
-------------------------------------------------------

Re: millisecond scheduler and CPU usage

On Sat, 06 Jan 2007 14:08:53 +0100, Denis Pousseur  
<denis.pousseur@compositeurs.be> wrote:

>
> Hi Jeff,
>
> All this explanations are very interesting.
>
> My approach, consisting of starting with a millisecond clock resolution,  
> is
> maybe a bad idea... In fact I have to schedule two kind of events :  
> regular
> events (for drawing counters and cursors) witch can really be scheduled  
> at a
> 1/100sec resolution and episodic events witch need to be scheduled at a  
> ms
> resolution (musical events).

I don't quite get it.
Why are you scheduling the musical event's yourself instead
of using the device driver? Same for the graphics really (for sprites).
Most of this is supported in hardware on most systems.
Seems to me you either rely on the existing drivers or write your own.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: millisecond scheduler and CPU usage

Well, this is a very long discussion... And I'm not sure it's the place here
to have it. 

The use of API such the AudioToolbox on Mac (I already use for some task,
for instance receive MIDI event in real time), is an option I consider
seriously. But the concepts who manages the musical devices in general share
all the same logic and philosophy based on an musical approach witch is
majority, certainly, but not unique. However, my work is especially to take
in count some considerations of a minority of composers the industry often
forget... It is why the logic of this kind of device is not easily
compatible with the soft I write.

Also, I store all my data into lisp objects. To work with a external
sequencer API supposes to store data in two formats with the terrific
increase of complexity this suppose when manipulate it... (or - but this is
a poor solution - to convert at start time, with the delay inherent and no
possibilities of real-time editing)

On the contrary, what I try to do is to convert the data from lisp to midi
events in real time during the scheduling. So the data don't need to be
stored two times, and it is always up to date, even when it is editing
during the sequencing process. For this point of view, it's really simpler
and more efficient.

So my choice is between two problematic solutions, and this choice is
difficult. It is why I ask some questions on this list before taking a
decision.

thank you for your advice !

Best

Denis

Le 6/01/07 15:26, « [NOM] » <[ADRESSE]> a écrit :

> On Sat, 06 Jan 2007 14:08:53 +0100, Denis Pousseur
> <denis.pousseur@compositeurs.be> wrote:
> 
>> 
>> Hi Jeff,
>> 
>> All this explanations are very interesting.
>> 
>> My approach, consisting of starting with a millisecond clock resolution,
>> is
>> maybe a bad idea... In fact I have to schedule two kind of events :
>> regular
>> events (for drawing counters and cursors) witch can really be scheduled
>> at a
>> 1/100sec resolution and episodic events witch need to be scheduled at a
>> ms
>> resolution (musical events).
> 
> I don't quite get it.
> Why are you scheduling the musical event's yourself instead
> of using the device driver? Same for the graphics really (for sprites).
> Most of this is supported in hardware on most systems.
> Seems to me you either rely on the existing drivers or write your own.
> 

-------------------------------------------------------
Denis Pousseur
70 rue de Wansijn
1180 Bruxelles, Belgique

Tel : 32 (0)2 219 31 09
Mail :  denis.pousseur@compositeurs.be
Website : http://compositeurs.be/Pousseur
-------------------------------------------------------