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

[Jacob Lifshay]

On Fri, Nov 13, 2020, 04:49 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
wrote:

> 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.
>
> examples:
>
> 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]
>

Funny you should mention that ... the simulator::WaitQueue class is unused,
waiting for events is not implemented.

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


That's more or less what is implemented currently, the Simulator class
doesn't even track dependencies, so is not a proper implementation of an
event-based simulator.

>
> 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():
>    pipes[pname].append(input[pname])
>    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).
>

Well, I've had no problem using Python sets ... since I started recently I
end up using the newly added features instead of limiting myself to things
Python had many years ago.

>
> 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():
>    pipes[pname].append(input[pname])
>    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.
>

one issue: the fetch pipeline is more complex than you might think, it
properly handles stopping fetching additional instructions when
encountering a taken branch since fetch pipelines usually can only fetch
consecutive instructions.

>
>
>
> 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)


One of the reasons I like Rust is they encourage using structs and traits
(kinda like Java interfaces but usually statically-dispatched and can be
implemented for any type, including external types) and composition rather
than deep class inheritance hierarchies -- it makes for less confusing code.

https://users.rust-lang.org/t/rust-koans/2408/2?u=programmerjake

>
>
> 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.
>

Yeah, I've definitely done that before, though I've often used bash instead
of python for that -- if it can't easily be done in bash the program is
probably complex enough that you'd want to do a more principled design.

>
>
> 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.
>

yeah, I get that.

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

Recompile time for me is on the order of 5s, which I'd consider acceptable
(though admittedly I have a high-end cpu with 24 threads).

>
> 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
> used.
>
> 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.
>

overcomplicated...

Jacob