Much improved, as predicted.
I ripped up the front of the tribot and replaced the jaws with an articulated
light sensor, which can sweep +/- around 60 degrees from center. It took quite a
while to figure out how to gear it and get everything solid enough; all these
new-fangled lego pieces I've not seen before.
This is what it does:
It's much faster than the last one -- when it gets it right, it can work out the
curvature of the line and steer exactly along it. When it loses the line, it
backtracks a little to find it. At the end of the video you can see the sensor
can't pick up the sharp turn in the line and the robot drives off into oblivion
(more work required).
On the programming side of things, I'm getting more used to the NXT environment.
I used two threads: one to control the sensor motor and one for the drive
motors. They communicate through two semaphores: the angle of the sensor motor,
and a flag that gets raised when the sensor has lost the line.
It probably would be feasible to do it in a single run-loop, albeit with more
state variables, and the NXT tool has fits with two many nested conditionals (it
also has fits about most other things, to be fair).
I find I have to change the tolerances of the light/dark sensing very carefully
to avoid incorrect readings. I have to adjust these tolerances throughout the
day, by trial and error, due to the change in ambient light. I still haven't had
any luck with the calibration.
Here's the source code; this time I've added some annotations that might give a
feel for what it's all about. Note that this is the only view of the program
you're given, and it can't be zoomed out (nor are there scrollbars...).
Richard writes:
How many light sensors can you have?
Alex writes:
The NXT can take 4 sensors, but it only comes with 1 light sensor. It can also
do bluetooth, so presumably you could expand it like crazy given the money +
willpower + blessing of the programming gods.
First Mindstorms robot. Here it is in action:
I started out with the tribot, which has building instructions but no real
programs. I had to rip up the front of it to move the light sensor further from
the floor -- in its initial position it couldn't tell the difference between
white and black.
You can show the current readings of the sensors on the device, which would be
handy when programming thresholds, but they don't seem to match up at all... so
it needed quite a bit of tweaking.
Here's the source code:
Lots of room for improvement...
This patch by Armin Rigo has been getting a lot of attention on the python-dev
list recently. From the description:
This is a port of PyPy's method cache optimization. It gives a very good
speed-up to PyPy, and it is simple enough to be attempted on CPython.
The patch introduces a global method cache, currently set to hold 1024 elements.
Each element in the cache looks like this:
struct method_cache_entry {
int version;
PyObject *name;
PyObject *value;
};
The struct is 12 bytes wide on 32-bit systems and 20 bytes wide on 64-bit
systems, making the table 12kb and 20kb large, respectively.
Each Python type is given a "version" number which is treated the same
as version numbers in Microsoft's Dynamic Language Runtime. Version numbers are
obtained from a global counter (so no two types share the same version number).
When a type is modified, that type's version number is refreshed (updated from
the global counter), as are the version numbers of all that type's subtypes.
When an attribute is looked up on a type (i.e., because it has failed lookup on
the object), the cache is first checked for the corresponding type's version
number, and the name of the method. The method cache is a hash table, with the
hash formed by the tuple (version, name).
If that attribute is not found in the method cache, lookup proceeds through the
MRO as usual; however that method will subsequently be cached before returning.
The entry in the method cache that occupies the same hash location will be
tossed.
The version number is a 32-bit int, and wraparound is handled correctly (when
the global counter reaches 0 again, the method cache is cleared). The last time
I checked, Microsoft's DLR did not gracefully handle wraparound. Because type
modification is relatively rare, I believe the version number could be held in a
16-bit integer without performance penalty, and with a small memory footprint
benefit. I haven't tried this though.
Armin and the patch reviewers have been reporting a consistent 20% or better
performance improvement on total runtime of all applications, which is nothing to
be sneezed at. The patch is still under review but looks like it's heading for
inclusion in Python 2.6.
The technique is similar to method caching used in Smalltalk-80. All
implementations of Smalltalk use a global descriptor table which maps the (class,
method) tuple to the method object. The earlier implementations, up until 1983,
typically used global method caches like this one to decrease the cost of looking
in the global table. Since then, inline caches have been the typical approach,
such as in Smalltalk (1984), Self (1994) and the Microsoft DLR / IronPython
(2007).
No doubt in response to my post last month, TEN has stopped using the term
"full HD" to describe their new channel, which launches today.
Disappointingly the new channel offers little new content (one late night movie
most days, and repeats of Veronica Mars and Battlestar Galactica), and even less
timeshifted content (only the news, delayed by half an hour).
EBroadcast, with their larger-than-screen-sized banner ads, have the TEN HD
schedule; YourTV, with their sensibly-sized ads, have not yet added TEN HD or 7
HD.
Richard Jones writes:
The program guide for the regular Ten digital broadcast currently contains the
HD broadcast programming. Yay Ten.
Alex writes:
TEN seems to be overrun with amateurs at the moment. Last night:
* The audio went out of sync with the video for thirty minutes.
* A color gradient test pattern approximately 1/3 of the screen replaced the TEN
watermark several times for around 10 seconds each time.
* One ad was shown at the wrong aspect
* Many ads are still letterboxed instead of widescreen (not to mention the ads
that are 4:3 barn-doored, but I guess that's the advertiser's decision).
I was only watching for a cumulative time of less than 30 minutes, so I imagine
it only got worse than this. Also, the new HD watermark is _really_
distracting.
There's a hilarious thread running in python-list at the moment in which the OP
asks the question, "Is a fast Python possible?". It's staggering to
see how many people have such a poor grasp of Python's current limitations.
The first reply to this is, "You think Python is slow? Prove it."
(Side-note: I have a friend at uni who will ask for proof of anything he doesn't
like. For example -- Me: This game isn't very fun. -- Him: What? Of course it's
fun. Prove that it's not!)
A large bulk of the replies simply assert that Python is plenty fast enough --
faster than Java, many say -- and that if it were slow Google would be on Guido's
back to do something about it.
Their justification that Python is fast? A 4-line program that computes 36
Fibonacci numbers in some amount of time less than Ruby.
My response to the OP (Dear Virginia):
Yes, a fast Python _is_ possible, evidenced not by Lisp, as many posters seem to
think is relevant, but by Self (a language that shares many similarities with
Python), and recent innovations by Microsoft (which close the gap on
implementation differences between Python and Self).
However, improvements to Python's speed cannot come about through incremental
improvement to the virtual machine -- a significant portion of the VM needs to be
reimplemented from the ground up. It goes without saying that such changes would
not be compatible with existing Python extensions.
Improvements to Python's speed also cannot come about through ad-hoc efforts
such as Shedskin, which implements some subset of Python by type inference and
translation to C++. (This should be obvious to any casual observer: if Shedskin
were to implement all of Python while maintaining only a single level of
indirection per object, it would imply that Python is no more expressive than
C++).
Improvements to Python's speed _may_ come about through the PyPy project.
However, the work that has been done so far is largely orthogonal to JIT
compilation; I see no particular evidence that the existence of PyPy will ease
the development of a robust JIT compiler (besides the reimplementation of many
parts of the standard library in pure Python, which is welcome).
Improvements to Python's speed _may_ also come from Microsoft's IronPython team.
Their Python implementation uses some of the techniques necessary to achieve a
fast JIT compiler, however they do this within an interpreter running inside the
CLR (and so is only incrementally better than the C interpreter). A JIT
compilation from Python bytecode to native machine code would reap huge benefits,
especially in cache coherency. However, Microsoft are not currently in a
position to make this change, having invested themselves so thoroughly in the
.NET framework.
Anyway, I daren't post this back to the list, for fear of
Python-isn't-slow-dammit death threats (those Americans and their guns).
Richard writes:
Then they won't know any better.
Austin writes:
That's spot on.
I'm keeping my eye on Rubinius, which is a Ruby VM based upon Smalltalk. It'll
be interesting to see how it goes.
I'm amazed that IronPython is just an interpreter for Python written on CLR. I
would've thought they'd at least do some direct Python bytecode compilation.
Alex writes:
I was a bit misleading in calling IronPython an interpreter. From what I
understand, the Python AST is compiled into CLR bytecode. That bytecode makes
heavy use of the Dynamic Language Runtime, so that a single CPython bytecode is
equivalent to several CLR bytecodes which either inline DLR operations or make
calls into the library. This is necessary because of Python's unusual treatment
of local variables, for example.
I ripped up the front of the tribot and replaced the jaws with an articulated
light sensor, which can sweep +/- around 60 degrees from center. It took quite a
while to figure out how to gear it and get everything solid enough; all these
new-fangled lego pieces I've not seen before.
This is what it does:
It's much faster than the last one -- when it gets it right, it can work out the
curvature of the line and steer exactly along it. When it loses the line, it
backtracks a little to find it. At the end of the video you can see the sensor
can't pick up the sharp turn in the line and the robot drives off into oblivion
(more work required).
On the programming side of things, I'm getting more used to the NXT environment.
I used two threads: one to control the sensor motor and one for the drive
motors. They communicate through two semaphores: the angle of the sensor motor,
and a flag that gets raised when the sensor has lost the line.
It probably would be feasible to do it in a single run-loop, albeit with more
state variables, and the NXT tool has fits with two many nested conditionals (it
also has fits about most other things, to be fair).
I find I have to change the tolerances of the light/dark sensing very carefully
to avoid incorrect readings. I have to adjust these tolerances throughout the
day, by trial and error, due to the change in ambient light. I still haven't had
any luck with the calibration.
Here's the source code; this time I've added some annotations that might give a
feel for what it's all about. Note that this is the only view of the program
you're given, and it can't be zoomed out (nor are there scrollbars...).
First Mindstorms robot. Here it is in action:
I started out with the tribot, which has building instructions but no real
programs. I had to rip up the front of it to move the light sensor further from
the floor -- in its initial position it couldn't tell the difference between
white and black.
You can show the current readings of the sensors on the device, which would be
handy when programming thresholds, but they don't seem to match up at all... so
it needed quite a bit of tweaking.
Here's the source code:
Lots of room for improvement...
Richard writes:
How many light sensors can you have?