Spending a Million on RISC OS

If you need to do some processing that takes time, you have to use Wimp_Poll so that you get null events, and can time-slice your processing so as not to hog the CPU.

Would not this be simpler with a timed null event?

You only need Wimp_PollIdle if you need to get null events at intervals.

Ah, yes :)

If the latter, then you need druck’s GraphTask.

A very good application, but not compatible with some new modes and not so easy (licence, use) to integrate in an existing Basic application.

For newcomers, there is a big difference between a Wimp application, a CLI application and a CLI application that works inside GraphTask.

That would be WimpBasic then. Not really a current option, though.

I was thinking of something older, more similar to RealBasic.
(can’t remember the name).

Or you can do it quicker with a version of Toolbox BASIC I just happen to know about.

???

If you need to do some processing that takes time, you have to use Wimp_Poll so that you get null events, and can time-slice your processing so as not to hog the CPU.

Would not this be simpler with a timed null event?

No, because a null event returned by Wimp_PollIdle is a timed null event. When calling Wimp_PollIdle the program gives the earliest time that it wants the call to return a null event. It’s not too difficult (in C¹) to package up a callback scheduler from this: NetSurf has one, and the idea might easily form part of a more general event handling library.

¹ It’s less fun in BASIC, of course – but then most things after Hello World are.

No, because a null event returned by Wimp_PollIdle is a timed null event.

I know, but he was talking if a classic Wimp_Poll, and I ask “why not a Wimp_PollIdle?”

To give more time to other tasks, it seems to be better, no?

It’s less fun in BASIC, of course – but then most things after Hello World are.

Cruel. ;-)

When I mentioned my Call module earlier last year in c.s.a.programming, Justin Fletcher berated me for using OS_CallAfter and OS_CallEvery inappropriately. At the time I was not completely convinced, but having re-read his (long) explanation, I think he is right. This should not be surprising, and he suggested that any programmer worth their salt shoud be able to produce scheduling routines for Wimp_PollIdle.

So, I thought I would have look at this again. It is not pretty in BASIC and it does not come simply, but I now have a small scheduling library, and it was fun to write.

Perhaps the trickiest thing to manage in BASIC is memory allocation. DIM is a blunt weapon, because blocks cannot be reclaimed. I have a routine for using memory above HIMEM the same way that Basalt does, but that is a bit clunky in pure BASIC. So, for this I have eventually employed a method I thought up many moons ago, to use the string allocation table.

The result is at:

http://kappa.me.uk/Miscellaneous/swPollIdle.zip

I welcome comments.

I welcome comments.

OK, here is a small self-contained RiscLua program that, I hope, does what the BASIC program does.

local sys, dim in riscos
local task in (require "wimp.task")
local schedule = {
 stop = 2000; -- cutoff time
 insert = \ (self, x) self[1 + #self] = x end;
 tick = \ (self, this)
   local last = this.time
   local time = sys "OS_ReadMonotonicTime"
   for i, event in ipairs (self) do
     local t, every, action in event
     if time - last > t then
       if action then action ( ) end -- if
       event.t = t + every
     end -- if
   end -- for
   => time - last > self.stop
   end;
}
local mytask = task ("Mytask", true)
local say = \(s) => \( ) mytask:report (s) end end
local nullevent = 0
do --------------------------[
 local _ENV = mytask
 b = dim (256); mask = 0x970
 time = sys "OS_ReadMonotonicTime"
 handler[nullevent] = \(self) => schedule:tick (self) end
 preclosedown = \(self) => self:report "finished" end
end ---------------------------]
schedule:insert {t = 200, every = 400, action = say "ok "}
schedule:insert {t = 300, every = 300, action = say "hello "}
schedule:insert {t = 400, every = 100, action = say "goodbye "}
mytask:init ( )
mytask:run ( )

The schedule object is a table – its list part consists of events which are tables with keys:

1. t (number – initial delay)
2. every (number – repeat interval)
3. action (function – to call when triggered)
   See the arguments to schedule:insert before the task is initialised and run. The method schedule:tick is there to provide the nullevent handler. The value schedule.stop is there to give a cutoff time.

I don’t claim this is anything more than a sketch. It does show how a list of scheduled actions can be written using RiscLua’s current wimp.task library without any further explicit memory-handling.

Thanks Gavin.

I cannot say I fully follow the Lua, but I do have some questions, based on what I had to consider for the BASIC.

First, does this call Wimp_PollIdle? I can only see one mention of a mask and that seems to be set to allow all NULL events. Also, the schedule object seems to take action on those events by searching for the earliest actionable event in the table every time. This seems excessive.

Second, once an event is added to the table, is it ever removed? You only have every type events, not after, although I like the delay. If a program repeatedly adds events, does this not constitute a memory leek?

One thing I missed in my library is a Schedule_Remove, but that is straightforward and I will do it later. After events are removed when they have been actioned.

does this not constitute a memory leek?

Look at it in the round and it’s an onion :)

Sorry, some typo’s just do that for me.

does this call Wimp_PollIdle?

Yes. If the second argument of task is nil then Wimp_Poll is used, and otherwise Wimp_PollIdle. This is all hidden away in the details of the wimp.task library. I had not given much thought to the mask; I used bits of the !Eph example in the RiscLua distribution.

This seems excessive.

I agree. The code is only acceptable for small lists of scheduled events. I had been thinking a bit about this. My first idea, which was probably too clever or not clever enough, was to work out the highest common factor of the delay times and to set this as a polling interval. Another idea was to order the list using a method:

 order = \ (self) table.sort (self, \ (x, y) => x.t < y.t end) end;

 remove = table.remove;

 schedule:remove (i)

perhaps we really need a Wimp version of BBC Basic :)

That would be WimpBasic then.

I wouldn’t call WimpBasic “A Wimp version of BBC Basic”. I’d call it a Wimp version of Basic, with a dialect familiar to users of BBC Basic.

I had not given much thought to the mask

I thought it worthwhile to mask NULL when there are no timed events. Then it is equivalent to Wimp_Poll. However, there is no provision for untimed NULLs, so I will have to think on this.

Another idea was to order the list using a method

But that requires a sort each time you add an event, doesn’t it? That is not much of a problem, but the ordered linked list I used allows events to be inserted without disturbing anything else. Can Lua do such structures?

If I read correctly, Lua does garbage collection, so there is no penalty when removing items, which has to be much more considered with BASIC.

However, there is no provision for untimed NULLs, so I will have to think on this.

I have thought. ;-)

AFAICS using timed events (with PollIdle) and returning all NULL events (with Poll) for a long processing job are incompatible. The answer is to use a very short interval timed every event, I think.

One thing I missed in my library is a Schedule_Remove, but that is straightforward and I will do it later.

If anyone is interested, I have updated the files at:

http://kappa.me.uk/Miscellaneous/swPollIdle.zip

I welcome comments.

No problem.

“PWP – 404 Error
This Page Cannot Be Found”

:)

I wouldn’t call WimpBasic “A Wimp version of BBC Basic”. I’d call it a Wimp version of Basic, with a dialect familiar to users of BBC Basic.

Exactly! Just to make input, print, plot, mode, the same way you do without Wimp (and without the help of an external module/application).

The answer is to use a very short interval timed every event

Or to have a system that can generate timed callbacks, to call your code (or opcode for Basic) exactly and only when needed… IMHO, it would use less resources than to check if it’s time to make something.

But that’s a completely different approach.

I get a 404 error at http://kappa.me.uk/Miscellaneous/swPollIdle.zip.

Can Lua do such structures?

Yes – linked lists of various flavours can be constructed using tables, though very often it is not necessary. A doubly-linked list would be constructed out of tables with three fields, previous, next, value, for example. In fact anything you can do with pointers is possible, so long as you realize that you may not be dealing with arrays of consecutive bytes.

A propos removing items from lists: if you are iterating over a list you have to be careful not to alter the list during the iteration. Instead you must collect a list of actions to be done to the list and then execute them when the iteration has completed.

If I read correctly, Lua does garbage collection.

Yes. If you have a table t then setting t[x] = nil ensures that the storage for t[x] will be collected. I tell a convenient lie, because it depends on what kind of a table t is and what kind of a key x is; see weak references in the Lua Manual.

I guess the following problem must be a computer science classic:
given an ordered list of numbers

 t_1 < t_2 < ... < t_n

 t_i <= t < t_[i+1]

Sorry, finger trouble when copying the replacement zip. Should be ok now.

I guess the following problem must be a computer science classic:

That looks quite similar to the scheduling PollIdle problem. ;-)

I have self-studied some computer science, but I could not give an answer. What is it?

What is it?

I am guilty of oversimplifying the problem because the list is varying in time. The earlier members disappear and newer members are being created. Otherwise I would say that we need a binary tree – compare t with the value at the root; if it is less, pass to the left subtree, if greater to the right. This makes for log_2(n) comparisons if the list has size n. But the time variation brings in a new aspect. We do not want to be spending the whole time rebuilding the tree to accommodate new events. Each every event spawns an arithmetic series of future times – after events spawn nothing. But actually there is nothing sacred about arithmetic series. We can just as well imagine an event whose action at a given time returns the next time to be scheduled – possibly in an uncomputable way. For example, the action might involve reading input and distilling a new time from that; I think the word oracle is used for such a circumstance. A proper analysis would consider the probability distributions of the intervals generated by an event. I think we may be drifting into deep waters with only a rubber ring to keep us afloat!
Anyway, I will have a crack at rewriting the schedule object using linked lists. Your approach seems to me now to be the best.

Thanks for the lesson. I am holding on to my rubber duck. ;-)

I will have a crack at rewriting the schedule object using linked lists.

It would be exceptional to have very many events on the go at once, so the cost of traversing the list is likely to be small and is only borne when the event is first created. Anyway, in pure BASIC linked lists are relatively easy, and also in assembly – the BASIC module is full of them.

compare t with the value at the root; if it is less, pass to the left subtree, if greater to the right. This makes for log_2(n) comparisons if the list has size n.

Uhh… … … … Do you have a version with cartoon pictures?

with cartoon pictures?

A happy thought. Somebody must have made a nice animated lecture to demonstrate the virtues of binary trees. Unless I dreamed it, I think there was a BASIC demo program on the BBC B to illustrate their speedier lookup properties.

Exactly! Just to make input, print, plot, mode, the same way you do without Wimp (and without the help of an external module/application).

Or to have a system that can generate timed callbacks, to call your code (or opcode for Basic) exactly and only when needed […] But that’s a completely different approach.

But I still do not understand what you think can be done. A program cannot respond to an OS timer call unless it is paged in. The Wimp has control of that, so let the Wimp do the timing.

As for calling BASIC (‘opcode’ what is that?), apart from the technical problem of executing a routine from outside a BASIC environment there is the problem of program flow. On the other hand, BASIC can easily respond to the Wimp through polling.

My best guess at what you are after is a single-tasking BASIC program that can respond to some form of timer interrupt, but nevertherless displays its output in a window. If GraphTask does not do it for you, then “Dream On”. ;-)

By the way, ‘WimpBasic’ is an existing commercial product, and Vince is quite right about its relationship to BBC BASIC.

I did many time this kind of thing. You put a callback on some part of you C code and fire a timer event. When the time is over, the timer call your C code at the right place.

It’s much better – IMHO – than polling many time from you C code to see if it’s the right time to make an action. With opcode, I suggest the same for Basic opcodes. Locomotive Basic on Amstrad worked like this with external timers able to call a specific Basic function after some time. Perhaps that the glue was inside the Basic interpreter and not AMSDOS, but who care? It worked like this: On Timer or Every, and let’s go.

That’s not a ‘dream’. I saw it, I used it, and still use it. The only closed equivalent in ROS seems to be WimpCallIdle. You still need to manage the events, but it’s better than nothing (even if it’s not as cool as a true Timer event… since it’s more a delay than a precise timer). Under the CLI, there is nothing.

My best guess at what you are after is a single-tasking BASIC program that can respond to some form of timer interrupt, but nevertherless displays its output in a window.

No. Two different subjects here (even 3). The timer/every problem is one. Wimp is another. I was answering to Vince about the possibility to have a wimped Basic, just for classic commands, and without GraphTask (just wimped by itself). Not at all a clone of WimpBasic. I did not talk of WimpBasic anyway. For true wimp application, it’s another subject. I would talk here of a clone of RealBasic, as the tool made for the Archimedes a long time ago (can’t remember the name).

Here are my thoughts on scheduling with computed time intervals.
I hope the RiscLua notation is acceptable.

Let us call an event a pair consisting of a number (a time)
and an increasing function from numbers to numbers, possibly
with side effects. Thus

   ev0 = { t = t0, f = f0 }

         sched = { val = ev1,
             p = { val = ev2,
             p = { val = ev3,
             p = nil }}}

is a linked list of three events, ev1, ev2, ev3. So p is the key
for next item in the linked list, val is the key for the event.

A schedule is ordered if ordering in the linked list coincides with
time ordering.

   ordered = \ (sched)
      if not sched then => true end -- empty lists are ordered
      ::loop::
      if not sched.p then => true end -- singleton list is ordered
      local ok = sched.val.t < sched.p.val.t
      sched = sched.p  -- move to next item
      if ok then goto loop
      => false
      end -- function

Ordered insertion (oinsert) of an event preserves the
property of being ordered.

    oinsert = (sched, ev)
          if not sched then => { val = ev, p = nil }
          local now = ev.t
          if now < sched.val.t then
             => { val = ev, p = sched }
          else
             => { val = sched.val, 
                  p = oinsert (sched.p, ev) } -- recurse
          end -- function

Triggering an ordered schedule means evaluating the function
of the first event, removing that event, and inserting a new
event at the later time returned by evaluating the function on
the present time.

   trigger = \ (sched)
          if not sched then => end -- if
          local t, f in sched.val
          => oinsert (sched.p, {
            t = f (t), f = f }) -- update schedule with new event
          end -- function

I’m confused. Are people proposing that an ordered linked list is an efficient data structure to use for representing the schedule, or are these just examples of how schedulers should work? There are much better data structures to use, e.g. a binary heap is a popular way of implementing priority queues – example here (although they’re not without their own fair share of flaws).

FWIW OS_CallAfter/OS_CallEvery is implemented using a sorted linked list. So popping the front item off the queue takes O(1), but insertion and deletion of arbitrary entries (including re-inserting CallEvery events) takes O(N) time. Luckily Acorn weren’t foolish enough to publish the details of the internal structure (unlike with OS_Heap), so it shouldn’t be too hard to swap it out for a better algorithm if we felt so inclined.

Are people proposing that an ordered linked list is an efficient data structure to use for representing the schedule,

Not this person, exactly. See my earlier remarks about binary trees. I was thinking about a more general notion of event, which computes the next time it is to be triggered, rather than being repeated at a set interval.

One will always want a pointer to the earliest event. But if the events are to be held in a binary tree, where is the root to be? Somewhere between the first and last, evidently, but the most efficient point will depend on the statistics of the repetition times that each event computes. This is where my brain starts to go fuzzy.

Thanks for the example, which looks interesting.

Are people proposing that an ordered linked list is an efficient data structure to use for representing the schedule,

Not this person, exactly. See my earlier remarks about binary trees.

Ah, I managed to miss that bit when skimming over the thread. From my point of view the discussion went straight from “what is the most efficient algorithm and data structure for storing an ordered sequence of events” to “here’s an implementation using a linked list” :-)

One will always want a pointer to the earliest event. But if the events are to be held in a binary tree, where is the root to be? Somewhere between the first and last, evidently, but the most efficient point will depend on the statistics of the repetition times that each event computes. This is where my brain starts to go fuzzy.

The most efficient place for the root of the tree is for it to be at the start, as with the binary heap example. The fun part is:

• Keeping the tree balanced (which is where binary heaps have an advantage over more naive binary tree implementations)
• Finding an efficient way of removing arbitrary events if they need to be cancelled before they fire. For binary heaps, the main problem here is the O(N) search to find the entry – but that’s fairly easy to solve by making the insert function return a pointer to an ‘event handle’ which can store a pointer to the entry in the heap (and make each heap entry itself store pointer to the event handle so it can be updated as the node moves through the tree).
• And for binary heaps another big problem is that the basic implementation will have a fixed maximum size caused by the fact it stores all the data in a linear array. Offhand I can’t think of any easy solutions to that which won’t end up increasing the time complexity of some of the operations.