Unoffical empeg BBS

Quick Links: Empeg FAQ | RioCar.Org | Hijack | BigDisk Builder | jEmplode | emphatic
Repairs: Repairs

Topic Options
#140791 - 06/02/2003 08:11 Linux internals question...
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
In working on my lyrics viewer project, I have come across a slight problem which I'd like to submit for consideration by the geekdom of this BBS. The problem is similar to what Richard Kirby was seeing while writing empacman, and is documented in this post. A gander at the empacman source shows that he didn't find a solution, or at least didn't implement constant FPS in v1 of empacman.

Richard's goal was to have a fixed frames per second in empacman, by having a timing loop which nanosleeps for a certain time (total frame time minus total time spent doing useful stuff). He was seeing that in reality, each iteration of the loop was taking more than he expected it to. For the lyrics scroller, it's not "frames per second" per se that I'm worried about, it's more a question of "I have one second to get this piece of text to this part of the screen before the next line draws." In my logic, no matter where the current line is, when the timestamp of the next line comes, it's going to be drawn. If the current line is behind for any reason, the next line is going to be drawn "on top" of the last one as it tries to scroll to the left. But, fundamentally, the loop algorithm Richard and I have is the same, my "frames per second" just changes with each line of lyrics.

Back when he originally asked this question, I suggested he try to use realtime scheduling. This turns out not to help out very much. It's important to realize that the sleep times we're talking about are rather small. Richard was expecting each loop iteration to take 1 second / 30 frames, or 33 milliseconds. The intervals I need for smooth (moving one pixel per frame) scrolling of the lyrics are sometimes smaller, sometimes down around 15ms. With sleep times this small, they seem to take longer than I want them to, just as Richard was seeing.

I think I may have found the reason why this is happening... Since Linux timeslices are 10ms (that's true on ARM as well, right, Mark/Hugo/Peter?) it seems logical that if I ask for a sleep time of, say, 15 ms, it's going to say "ok, fine, while you're sleeping, I'm going to schedule you and do some useful work for someone else." If that happens, it seems that the "sleep time" wouldn't necessarily be accurate. Lo and behold, the nanosleep man page documents this bug:


BUGS
The current implementation of nanosleep is based on the normal ker-
nel timer mechanism, which has a resolution of 1/HZ s (i.e, 10 ms
on Linux/i386 and 1 ms on Linux/Alpha). Therefore, nanosleep
pauses always for at least the specified time, however it can take
up to 10 ms longer than specified until the process becomes
runnable again. For the same reason, the value returned in case of
a delivered signal in *rem is usually rounded to the next larger
multiple of 1/HZ s.

As some applications require much more precise pauses (e.g., in
order to control some time-critical hardware), nanosleep is also
capable of short high-precision pauses. If the process is scheduled
under a real-time policy like SCHED_FIFO or SCHED_RR, then pauses
of up to 2 ms will be performed as busy waits with microsecond pre-
cision.

.

So that sounds like the culprit, right? Great. Now what to do about it? Going to SCHED_FIFO or SCHED_RR, as the man page suggests, is only going to help me if my sleep times are sub 2ms, where the kernel will just busy-wait instead of scheduling me. My sleep times are rarely that small, though, so even with one of those policies, I'm going to get scheduled, and the resolution of the nanosleep is far too coarse, resulting in loops which take too long, and, in my case, lyrics which are printed on top of each other on the screen.

Basically, if my analysis is right, empacman and emphatic are both falling prey to the fact that our sleep times are too big for Linux to bother giving us an accurate return, but sufficiently small that the error factor is a large enough percentage of the total loop time that it causes visible problems.

So what do I do to get around this bug, and still get smooth scrolling? The workaround is, of course, to skip two pixels instead of just one when drawing, and double the sleep time, effectively halving the frame rate. That works fine. But I want *smooth* scrolling if I can find a way to do it.

Could I just write a busy-wait loop which keeps calling gettimeofday() until the specified time has elapsed? That seems like it might work, but could starve other processes. Would a busy-wait loop with a sched_yield() inside it be any better than a nanosleep? I want this thing to be efficient, but I really need a way to delay my loop that's going to give me better than 10ms resolution to get really smooth scrolling of very fast lyrics. Anyone have any ideas?
_________________________
- Tony C
my empeg stuff

Top
#140792 - 06/02/2003 08:19 Re: Linux internals question... [Re: tonyc]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
How about using a nanosleep() less than 2ms multiple times to add up to your 15ms? You'd probably have to check the time at each return and recalculate for any overage, but that doesn't sound too outrageous.
_________________________
Bitt Faulk

Top
#140793 - 06/02/2003 08:22 Re: Linux internals question... [Re: wfaulk]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
Interesting hack... Might give that a shot. But let's say I did 15 1ms nanosleeps... Couldn't the kernel decide to context-switch me in-between any one of them?
_________________________
- Tony C
my empeg stuff

Top
#140794 - 06/02/2003 08:28 Re: Linux internals question... [Re: tonyc]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
That I don't know. Obviously, you'd have to be in a realtime priority to get it to work at all, so I'd suspect that it's would at least be less frequently. And it's not like the lyrics viewer is controlling a space shuttle or anything. I think we could deal with the rare to occasional text overlap.

BTW, I must have missed something somewhere. Why are you rewriting a lyrics viewer? What happened to the other one that was just announced? Or are you just fixing up some stuff?
_________________________
Bitt Faulk

Top
#140795 - 06/02/2003 08:28 Re: Linux internals question... [Re: tonyc]
tman
carpal tunnel

Registered: 24/12/2001
Posts: 5528
Unless you give it such a high priority that it never schedules anything else you're always going to end up with this problem.
If you're doing anything that requires realtime response then it's going to be difficult. It's going to be hard to give emptris/whatever enough CPU time and also allow the player to do the actual MP3 decoding as well.

- Trevor

Top
#140796 - 06/02/2003 08:52 Re: Linux internals question... [Re: wfaulk]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
Yeah, we *can* obviously deal with the occaisonal overlap, but it's not like we're hurting for free CPU. The player on average seems to use 30-45%, and the lyrics scroller is using 4% at most. There's spare CPU cycles to be had, they're just not being spent in the right place. Yes, I'm being a perfectionist somewhat here, but it seems like if there's a resource there, and nobody else needs it, I should be able to get it, and, more to the point, the sleep times should be more accurate than the 10ms kernel timeslice interval.

As for what I'm doing, you did miss something. I am continuing development of the lyrics scroller that Patrick Giasson wrote and released a few weeks ago, although at this point, it's hard to say my code looks like his anymore. He released it with a few known problems, and I've tried to fix them. I've also added true ID3v2 synchronized lyrics support, and have fixed issues related to detecting rewinds/fast forwards, song changes, etc, which the original version didn't handle very well. He has said he'd like to focus on a Winamp or XMMS plugin for adding the timestamps to the lyrics, and since I'm more experienced as a C programmer, I offered to do more of the primary development of the scroller. So that's where we're at.
_________________________
- Tony C
my empeg stuff

Top
#140797 - 06/02/2003 08:57 Re: Linux internals question... [Re: tman]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
Unless you give it such a high priority that it never schedules anything else you're always going to end up with this problem.
If you're doing anything that requires realtime response then it's going to be difficult. It's going to be hard to give emptris/whatever enough CPU time and also allow the player to do the actual MP3 decoding as well.


See, I don't think that's the case. Even when I run with SCHED_FIFO and highest priority, the same problem occurs. The lyrics scroller isn't chewing up tons of CPU, nor is it asking for guarnateed microsecond-level sleep resolution. All I need for this application is to sleep for, say, 15 milliseconds, instead of "somewhere between 15 and 25 milliseconds" which is what this nanosleep bug ends up doing. I don't need exact realtime response, but to ask for 15 ms and get back something that can be 40% higher is far from ideal.
_________________________
- Tony C
my empeg stuff

Top
#140798 - 06/02/2003 08:59 Re: Linux internals question... [Re: tonyc]
genixia
Carpal Tunnel

Registered: 08/02/2002
Posts: 3411
I don't know the answer to your question. But I wonder if the problem might be dealt with by a timer interrupt and a double-buffered screen? The empeg's display is updated at a fixed 40Hz rate IIRC.
_________________________
Mk2a 60GB Blue. Serial 030102962 sig.mp3: File Format not Valid.

Top
#140799 - 06/02/2003 09:02 Re: Linux internals question... [Re: tonyc]
wfaulk
carpal tunnel

Registered: 25/12/2000
Posts: 16706
Loc: Raleigh, NC US
You might also try a select(0, NULL, NULL, NULL, timeout) where timeout is set to 15ms. I don't know that that would work better and I don't have a Linux machine's manpages here to see if there are bugs listed there, either. But it's worth a shot, potentially.
_________________________
Bitt Faulk

Top
#140800 - 06/02/2003 09:11 Re: Linux internals question... [Re: tonyc]
tman
carpal tunnel

Registered: 24/12/2001
Posts: 5528
What you're asking would be solved if you used RTLinux or something which would guarantee that if you wanted to sleep for 15 milliseconds then it will wake the process in 15 milliseconds. You can't guarantee this in normal Linux. I guess you could do it at a kernel module and use some periodic interrupt. Not quite the easy solution you're looking for though.

- Trevor

Top
#140801 - 06/02/2003 09:25 Re: Linux internals question... [Re: tman]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
Yeah, RTlinux is obviously overkill for this particular application.

Tonight I'm going to try to do it with a busy-wait loop (only for the short delays, for the longer ones I'll still nanosleep) and see where that gets me. Theoretically I guess I could still be switched out, but probably not often enough to throw things off.
_________________________
- Tony C
my empeg stuff

Top
#140802 - 06/02/2003 12:11 Re: Linux internals question... [Re: tonyc]
mcomb
pooh-bah

Registered: 31/08/1999
Posts: 1649
Loc: San Carlos, CA
What about just checking the time before and after the nanosleep and if it lasted longer than expected bumping the text two pixels instead of one? That would keep you from burning excess CPU and (assuming this problem doesn't happen for every call) still keep the scrolling relatively smooth.

-Mike
_________________________
EmpMenuX - ext3 filesystem - Empeg iTunes integration

Top
#140803 - 06/02/2003 12:41 Re: Linux internals question... [Re: mcomb]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
What about just checking the time before and after the nanosleep and if it lasted longer than expected bumping the text two pixels instead of one?

I was doing that for a while. That approach does work, but the key word is "relatively" smooth. It's noticable (to me) when it has to "catch up." I was just trying to explore every avenue to get it to scroll smooth all the time. If I can't find the holy grail, then I'll put the "skip a pixel" code back in.
_________________________
- Tony C
my empeg stuff

Top
#140804 - 06/02/2003 12:55 Re: Linux internals question... [Re: wfaulk]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
You might also try a select(0, NULL, NULL, NULL, timeout) where timeout is set to 15ms

Hmmm.. Now those results are interesting. I can't test that on my empeg right now at work, but on my i686 Linux box at home, a select seems to give me results that are a lot closer than using nanosleep. I'll have to try that out once I get home.

This begs the question why select() would have a more accurate timeout mechanism than nanosleep()...
_________________________
- Tony C
my empeg stuff

Top
#140805 - 06/02/2003 13:08 Re: Linux internals question... [Re: tonyc]
tms13
old hand

Registered: 30/07/2001
Posts: 1115
Loc: Lochcarron and Edinburgh
This statement from developer section on RioCar.Org may be of interest:

"It is further possible to buffer and synchronize screen updates with the audio DMA, but documentation of this feature is not yet available."

Perhaps there are some hints in the display driver source code?
_________________________
Toby Speight
030103016 (80GB Mk2a, blue)
030102806 (0GB Mk2a, blue)

Top
#140806 - 06/02/2003 13:14 Re: Linux internals question... [Re: tms13]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
"It is further possible to buffer and synchronize screen updates with the audio DMA, but documentation of this feature is not yet available."

Perhaps there are some hints in the display driver source code?


Hmm... Interesting concept. Though since user apps don't access /dev/display directly (Hijack does that) I would imagine such functionality would require Hijack changes. And then there's that part about ti being not-yet-documented... If there is some documentation of this ability in empeg_display.c or empeg_audio3.c, I can't make sense of it. Maybe if one of the empeg guys in the know happens to stop by this thread, they could shed some light.
_________________________
- Tony C
my empeg stuff

Top
#140807 - 06/02/2003 13:54 Re: Linux internals question... [Re: tonyc]
kirkis
new poster

Registered: 17/03/2002
Posts: 21
Good to see my old problems being revisited. My solution for empacman was to busy loop. I thought that busy looping would be a bad thing and steal too much cpu, but in practice it turned out okay - empacman is smooth most of the time but will pause whenever the player app decides that it needs the hardware most.

I'd be very interested in other solutions to this problem that are discovered. I think its quite a fundamental problem that many userland apps doing animation on the screen will face. If an ideal solution is found, maybe there is a way I can incorporate it into vfdlib to help other developers.

Cheers,

Richard
--

Top
#140808 - 06/02/2003 14:35 Re: Linux internals question... [Re: tonyc]
tman
carpal tunnel

Registered: 24/12/2001
Posts: 5528
From what I gather from reading the source you get a big queue of screen updates and another queue of audio data and you can tell the kernel to update both at the same time. This way the screen updates and the audio data is kept in sync.

Haven't poked around in the source for a while though so you might want to check to see if what I remember is correct.

There's definately no Hijack support for this though so you can't really use it at the moment without driving the display directly. And doing that would conflict with the player.

- Trevor

Top
#140809 - 06/02/2003 15:05 Re: Linux internals question... [Re: tman]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
Okay, well I can't understand kernel goings-on well enough to determine where said synchroni(s|z)ation mechanism lives... So we'd have to wait for Mark Lord's input on the situation. And since Mark is working on sleds right now, I wouldn't want to disturb him (well, at least not until I get my sled ). So if I can't find an acceptable solution on my own, I'll just release my program with whatever it's got, and save this for another day.
_________________________
- Tony C
my empeg stuff

Top
#140810 - 06/02/2003 15:11 Re: Linux internals question... [Re: tonyc]
jaharkes
enthusiast

Registered: 20/08/2002
Posts: 340
Loc: Pittsburgh, PA
sleep/nanosleep/select/poll all only give you one guarantee. You will sleep at least for the length of the timeout, but there is no reasonable upper bound. i.e. with 100 CPU bound processes you might have to wait up to a full second.

What you probably want is to 'busy loop without hogging the CPU'. You can do this with sched_yield() and checking how long we were out with gettimeofday.


#include <sys/time.h>
#include <sched.h>
void busy_loop_until(struct timeval *when)
{
struct timeval now;
while(1) {
gettimeofday(&now, NULL);
if (timercmp(&now, when, >=) break;
sched_yield();
}
}

It will just burn some (unused) CPU cycles when nothing else is runnable.
_________________________
40GB - serial #40104051 gpsapp

Top
#140811 - 07/02/2003 07:06 Re: Linux internals question... [Re: tonyc]
peter
carpal tunnel

Registered: 13/07/2000
Posts: 4172
Loc: Cambridge, England
I can't test that on my empeg right now at work, but on my i686 Linux box at home, a select seems to give me results that are a lot closer than using nanosleep.

That could be because, unlike an Empeg with the player software running, your i686 Linux box doesn't have a large number of SCHED_RR threads running, some of them doing sporadically CPU-intensive tasks.

That's also why, on the player, having another process busy-waiting at normal priority doesn't hose playback. Most of the player is SCHED_RR which means that if it's runnable, it runs and you don't, end of story.

Busy-waiting at SCHED_RR is quite definitely a bad thing.

Peter

Top
#140812 - 07/02/2003 08:30 Re: Linux internals question... [Re: peter]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
Yeah, I am at least smart enough to not combine realtime scheduling with busy-waiting. I have actually ditched the idea of using RR or FIFO scheduling, since it ends up not helping me for what I'm doing.

For what it's worth, I've abandoned any hopes of getting accurate sleep times. I've compensated in my program by just delaying the start of the next line a little if things are behind. This isn't ideal, but even using busy-waiting, I couldn't get the lines to end up where they needed to be. The result is lines never run into each other, but if the player goes to disk to fill up its cache, the lyrics might stutter a little bit.

Anyway guys, things are looking real good for a release this weekend, folks, including the fact that there's 8 inches of snow here. Last night I added a little menu to change the font, position, etc. of the lyrics, and I'm going to add a "fullscreen" mode where it scrolls the lyrics vertically. This has been by far the most fun empeg project I've done.
_________________________
- Tony C
my empeg stuff

Top
#140813 - 07/02/2003 08:40 Re: Linux internals question... [Re: tonyc]
oliver
addict

Registered: 02/04/2002
Posts: 691
sweet... i could never get the original lyrics view to work, can't wait for you to release your modified version!
_________________________
Oliver mk1 30gb: 129 | mk2a 30gb: 040104126

Top
#140814 - 07/02/2003 11:14 Re: Linux internals question... [Re: oliver]
tonyc
carpal tunnel

Registered: 27/06/1999
Posts: 7058
Loc: Pittsburgh, PA
Yeah, I'll try to get together a proper install script for it. The one thing I should mention is that I'll be including a utility for adding lyrics which are in LRC text file format (like the ones here) but I have not yet found any WinAMP plugins which do this. There is an XMMS plugin called SingIt! which looks like it might work, but I haven't tried it yet. Also, an XMMS plugin won't be helpful for Windows users.

So what people would have to do is use one of those "other" WinAMP lyrics plugins that give you the option to save a LRC file instead of embedding the lyrics in a Lyrics3 tag. Then they'd have to run my command-line program to parse out those lyrics and add them to the real ID3v2 tag. A WinAMP plugin that can write ID3v2 SYLT frames directly would be ideal, but I'm not much of a Windows developer these days. Patrick (the guy who did the first implementation of the lyrics scroller) mentioned that he might try to write a plugin, but I haven't heard any news on that front.


Edited by yn0t_ (07/02/2003 11:16)
_________________________
- Tony C
my empeg stuff

Top