[Libre-soc-dev] daily kan-ban update 10nov2020

Luke Kenneth Casson Leighton lkcl at lkcl.net
Fri Nov 13 12:49:03 GMT 2020

On 11/13/20, Jacob Lifshay <programmerjake at gmail.com> wrote:

> So, what approach would you have used? I can't think of a way to do that in
> 250 lines (excluding cheating by having 1500 character lines or similar).


data structures.


the 80 lines of the simulator.h Queue class is entirely replaced by
the use of a 1 line pattern placing list entries into an OrderedDict.

d[simtime] = d.get(simtime, []) + [value]

or drop the concept of event-driven simulator entirely, use in-place
state, and extract the current state to create new columns on each

this by having a list of instructions each with "state".  a forloop on
finding that the instruction is not yet issued appends an empty string
to the output column for that cycle.

a simple string would suffice to indicate the state (having the
advantage that it is self-explanatory and needs less code when adding
to the output table)

knowing that the code is throwaway and not a result-generating
simulator all immediates can be dropped entirely from the code.

also knowing that results are not to be created the only thing that
need be passed down FU pipelines is the output register names.  this
can be done with a dictionary of lists with push and pop.

one/two lines to set them up (right length, all empty), and a
two/three-line forloop to perform pushes (into pipeline) and pop the
results (out of pipeline)

pipesizes = {'LD': 2, 'ADD': 1}
for pname, plen in pipesizes.items():
   pipes[pname] = [None] * plen

res = {}
for pname, plen in pipesizes.items():
   res[pname] = pipes[pname].pop(0)

also knowing that instructions are not result-generating and also to
save code the instructions can be specified in a pre-formatted fashion
that is still clear:

* name outputs inputs
* ['ADD', ('r9',), ('r9', 'r3')]
* ['BR', ('CTR',), ('CTR',)]

no result computation means that an actual regfile is not needed. a
"rename" dictionary can store the last count and a simple function
increment it:

  d[regname] = d.get(regname, 0) + 1
  return "%s.%d" % (regname, d[regname])

(we need not worry about reallocation / reuse of WaW regs after they
drop through the pipelines, hence simply allocating a new one every
time with a 2 line function is perfectly sufficient).

looking up which (renamed) reg to use on RaW hazards is done by lookup
in the rename dict.

a set can be used to store WaR hazards.  (sets are not commonly
understood to even exist in python. most people would use a dict with
empty values).

if it turns out that we do not care where the result comes from when
it pops out the results can be dropped into a set:

res = set()
for pname, plen in pipesizes.items():
   res.add( pipes[pname].pop(0) )

the features of sets (union, difference) would help decide what to do
(with one keyword, not 4-5 lines of forloop)

another set can accumulate the regs needed to be written. a count on
this tells us how many REGFILE WRITEs are needed.

the generation of a line of markdown table is also 1 line (using
join).  two to three lines to create the table heading based on the
number of cycles.

with these ridiculously short patterns taking up no more than around
100 lines, the actual algorithm, the main loop, i would expect to be
no more than 150 lines, for an estimate of around 250.

an observation: not a single mention of a python "class" has been
made.  it is entirely using dictionaries and lists.

the only place where a class might be appropriate is the instruction
"state" and that can be declared "class Instruction: pass" followed by
dropping member variables into it on-demand (no init function)

classes with functions (including init) take up lines of code, and,
more than that, are concepts that take considerable effort to explain
to 15-year-olds (my brother dan is a teacher.  he's found that classes
make the average students heads spin)

this is an extremely effective "pathologically to the point" coding
technique that in no way has any room for "expansion".  no class
overloads are possible because there are no classes and this is
perfectly fine because further expansion and re-use is excluded from
the requirements.

a new algorithm which we want to try out, you literally copy the file
and edit the copy (keeping the old one so it can be run and used for
comparison purposes)

or throw it out and start again.  and this is again perfectly fine
because the code is so ridiculously short.

the technique is called "rapid prototyping" and it is an extremely
valuable skill to acquire.

the reason why there are so many messages is because you were not
responding.  if you had responded and engaged (even to say "i don't
understand" or "i don't agree" or "can you explain" or "i really would
prefer to explore X" all of which are absolutely fine) there would
have been less repetitions and therefore less messages.

the mental context-switching, environment setup time, compile-time of
c++, and the extra verbosity, these are all major hindrances.

an 80 line c++ queue class replaced by a 1 line python pattern using dict.get!

also: again: c++ is not something that average 15-17 year olds can
handle.  my brother can just about get away with helping his 16 year
old daughter to do programming exercises using python.

python is popular and stunningly effective for these types of
throw-away rapid prototyping tasks, because you get more done with
vastly less code *as long as* appropriate shortcut techniques are

i.e. *not* using type-declarations and only using classes if it makes
sense to do so.

remember the example i gave of an employee writing 16,000 lines of MVC
code (django) to replace 450 lines of code i had written to display
CPU usage in a web page.


More information about the Libre-soc-dev mailing list