Up to Main Index Up to Journal for August, 2024
JOURNAL FOR SUNDAY 18TH AUGUST, 2024
______________________________________________________________________________
SUBJECT: Adventures in AI + Tail call recursion optimizations in Mote
DATE: Sun 18 Aug 20:10:25 BST 2024
Recently, work life has been keeping me busy. I’ve continued to work on Google
training courses. I now have 36 skill badges in GCP, Kubernetes and Artificial
Intelligence.
Over the past week I’ve been focusing mostly on AI. It’s been… interesting…
Currently the computing world is hyped up on AI more than a toddler on a sugar
rush. If there is interest, maybe I’ll write more about my AI adventures in
the journal.
The language models (LLMs) I have been working with are gemma2:2b for general
work and llava for image analysis. My desktop has an Nvidia T1000 8Gb graphics
card. Not a top of the range power house, but it seems to fair quite well and
running models for AI tasks locally is quite usable.
Most of my work has centred around getting an AI to run locally — on modest
hardware, with no services or networking involved — and to experiment with the
AI to explore its capabilities, how best to interact with the AI and how the
AI might be put to use. I’ve even have the AI running on a Raspberry Pi 4 ;)
To that end I’ve been summarising my experiments into a presentation for my
colleagues. I’ll be showing how to get started installing the AI and some
basic prompt engineering: text summation, generating draft emails and other
text, determining sentiment and intent and some image analysis. I also have a
demo I’ve written integrating a Go web service with the AI. Hopefully all this
will encourage and motivate them to experiment on their own.
In other news…
Go 1.23 was released this week on the 13th August. I’ve not found the time yet
to take a look, however I have read the release notes. The main new feature
seems to be the range-over-func functionality, something I’m going to have to
look at sooner rather than later.
That’s enough about work life, let’s talk about Mote…
I’ve been working on Mote, the next version of my Mere programming language,
as time permits. Regular expression handling operators have been added with
copious tests. These are the same as implemented in the first version of Mere.
The “big ticket” item I’ve been working on for Mote is tail call recursion
optimizations. Tail call recursion is when the final operation in a function
is a ’return’ expression that calls the same function again. For example:
func fn
# do something interesting
return call fn
end
In the above code there is no need for the runtime to create a new call state.
The final return call requires no further information about the current call
and so the current state can be reused. By not saving a new call state for
every call there is less unwinding of the call stack later on. This improves
performance and reduces the runtime memory overhead. The first version of Mere
did not have this optimization.
For example, consider a simple recursive function:
println call repeat "*" 5
func repeat s n
is len s == n; return s
return call repeat s+s[0], n
end
When run, the above code produces:
>mote example.src
*****
>
Looking at the end of the trace for the above code, when optimizations are
turned off, we see:
Trace started (address, line, op/fn, args):
0x0000001F 6 return | s["…"] V[0x03:repeat∙s:s]
0x0000002B 7 return | s["…"] s["*****"]
0x0000002B 7 return | s["…"] s["*****"]
0x0000002B 7 return | s["…"] s["*****"]
0x0000002B 7 return | s["…"] s["*****"]
0x0000000C 3 println | s["…"] s["*****"]
The 5 ‘return’ operations are the stack unwinding from the recursive calls.
However, looking at the trace when optimizations are turned on we see:
Trace started (address, line, op/fn, args):
0x0000001F 6 return | s["…"] V[0x03:repeat∙s:s]
0x0000000C 3 println | s["…"] s["*****"]
Here we see that with optimizations turned on there is no stack unwinding.
Testing with a simple recursive factorial example, shown below, yields a 36%
improvement in performance:
for x = 1; x <= 20; x++
printf "%2d! = %d\n", x, call factorial x
next
println elapsed()["autoMicro"]
func factorial N
return call fn N 1
func fn N acc
is N == 0; return acc
return call fn N-1, N*acc
end
end
The optimization will work for multiple exit paths as well. For example
consider:
println call recur
func recur
is kind N == "undefined"; N = 0
N++
is N == 3; return N
is N == 2; return call recur N
return call recur N
end
Here we have two recursive calls to recur. One is taken if “N == 2” and the
other is the final default case. With optimizations turned off we see the
stack unwinding again:
Trace started (address, line, op/fn, args):
0x00000028 8 return | s["…"] V[0x03:recur∙N:i]
0x00000035 9 return | s["…"] i[3]
0x0000003C 10 return | s["…"] i[3]
0x0000000A 3 println | s["…"] i[3]
With the optimizations turned on there is no stack unwinding:
0x00000028 8 return | s["…"] V[0x03:recur∙N:i]
0x0000000A 3 println | s["…"] i[3]
I tend to use recursion a lot, so I’m quite happy with this change :)
The next step for Mote is to clean up some example programs I’ve been working
on. Then I need to get the new ICE (Integrated Code Environment) finished,
rewriting all of the information and example code is not going to be fun. Once
that is done I should be able to replace the current Mere version in the annex
with the Mote version.
Mere ICE in the annex will still be labelled as early access, but it will show
progress and allow people to have a play and experiment.
To end, a haiku generated by the AI, about AI:
Questions unanswered,
Algorithms ponder deep,
Truth waits in the code.
--
Diddymus
Up to Main Index Up to Journal for August, 2024