Portable Assembly

On 6/13/2017 10:26 PM, Reinhardt Behm wrote:
> AT Wednesday 14 June 2017 12:57, Don Y wrote:
>
>> Correct.  But, it's only "order of" assessments.  I.e., is this
>> a constant time algorithm?  Linear time?  Quadratic?  Exponential?
>> etc.
>>
>> There's a lot of handwaving in O() evaluations of algorithms.
>> What's the relative cost of multiplication vs. addition operators?
>> Division?  etc.
>
> I found many of such evaluation grossly wrong. We had some iterative
> solutions praised as taking much fewer iterative steps than others. But
> nobody took into account that each step was much more complicated and took
> much more CPU time, than one of the solutions that took more steps.
> And quite often the simpler solution worked for the more general case
> whereas the "better" worked only under limited conditions.

That doesn't invalidate the *idea* of modeling algorithms using some
set of "abstract operation costs".

But, it points to the fact that the real world eventually intervenes;
and, its a "bitch".  :>  Approximations have to eventually give way to
REAL data!

For example, I rely heavily on the (paged) MMU in the way my RTOS
handles "memory objects".  I'll map a page into another processes
address space instead of bcopy()-ing the contents of the page
across the protection boundary.  A win, right?  "Constant time"
operation (instead of a linear time operation governed by the
amount of data to be bcopied).

But, there's a boat-load of overhead in remapping pages -- including
a trap to the OS to actually do the work.  So, what you'd *think* to be
a more efficient way of handling the data actually is *less* efficient.

(Unless, of course, you can escalate the amount of data involved
to help absorb the cost of that overhead)

OTOH, there are often "other concerns" that can bias an implementation
in favor of (what appears to be) a less efficient solution.

E.g., as I work in a true multiprocessing environment, I want to
ensure a caller can't muck with an argument for which it has provided
a "reference" to the called function WHILE the called function is
(potentially) using it.  So, the MMU lets me mark the page as
immutable (even though it *should* be mutable) UNTIL the called
function has completed.

[This allows the caller to *access* the contents of the page
concurrently with the called function -- but, lets the OS
intervene if the caller tries to alter the contents prematurely.
The "write lock" has value that couldn't be implemented with the
bcopy() approach -- think of large objects -- and is "cheaper"
to implement once you've already decided to take the hit for
manipulating the page tables]

The "real machine" fixes values to all those constants (K) in the
O()-evaluation.  And, can muck with the decision making process
in certain sets of constraints.

On Wednesday, June 14, 2017 at 2:58:42 AM UTC-4, Don Y wrote:
> On 6/13/2017 10:26 PM, Reinhardt Behm wrote:
> > AT Wednesday 14 June 2017 12:57, Don Y wrote:
> >
> >> Correct.  But, it's only "order of" assessments.  I.e., is this
> >> a constant time algorithm?  Linear time?  Quadratic?  Exponential?
> >> etc.
> >>
> >> There's a lot of handwaving in O() evaluations of algorithms.
> >> What's the relative cost of multiplication vs. addition operators?
> >> Division?  etc.
> >
> > I found many of such evaluation grossly wrong. We had some iterative
> > solutions praised as taking much fewer iterative steps than others. But
> > nobody took into account that each step was much more complicated and took
> > much more CPU time, than one of the solutions that took more steps.
> > And quite often the simpler solution worked for the more general case
> > whereas the "better" worked only under limited conditions.
> 
> That doesn't invalidate the *idea* of modeling algorithms using some
> set of "abstract operation costs".
> 
> But, it points to the fact that the real world eventually intervenes;
> and, its a "bitch".  :>  Approximations have to eventually give way to
> REAL data!
> 
[]
> 
> The "real machine" fixes values to all those constants (K) in the
> O()-evaluation.  And, can muck with the decision making process
> in certain sets of constraints.

Exactly right!

The BIG-O notation too often is depicted as O() when it is
really O(n) where n is the input set size. What get lost sometimes
is people treat O(n) as a comparison at a given set size. and that
is the error. (I don't think you fall into this error, Don.)

BIG-O analysis allows you do do some testing at a data set size n1
and then make a rough estimate of the run time for n2 > n1.
this can be done for the hardware and processor instruction set.
Its purpose is to avoid the naive estimate:
 "I ran this on a data set of 100 and took 0.5 microseconds,
  so on the production run of 1,000,000 it should only less
  than a minute (50 seconds)."

Hopefully, folks here are not that naive to depend on just O(n).
Your point is very important and worth repeating:
 the analysis of algorithms can be more precise when it can
take into account the features of the implementation environment.
(I hope I phrased that close to what you meant.)

have a great day
  ed

Hi Ed,

On 6/19/2017 6:48 AM, Ed Prochak wrote:
> On Wednesday, June 14, 2017 at 2:58:42 AM UTC-4, Don Y wrote:

>> The "real machine" fixes values to all those constants (K) in the
>> O()-evaluation.  And, can muck with the decision making process
>> in certain sets of constraints.
>
> Exactly right!
>
> The BIG-O notation too often is depicted as O() when it is
> really O(n) where n is the input set size. What get lost sometimes
> is people treat O(n) as a comparison at a given set size. and that
> is the error. (I don't think you fall into this error, Don.)

It's helpful for evaluating the *relative* costs of different
algorithms where you assign some abstract cost to particular
classes of operations.  It is particularly effective in a
classroom setting -- where newbies haven't yet learned to THINK
in terms of the costs of their "solutions" (algorithms).

For example, one way to convert a binary number to an equivalent
decimal value is to count the binary value down towards zero (i.e.,
using a "binary subtract 1") while simultaneously counting the
decimal value *up* (i.e., using a "decimal add 1").  Clearly, the
algorithm executes in O(n) time (n being the magnitude of the number
being converted).

Other algorithms might perform an operation (or set of operations)
for each bit of the argument.  So, they operate in O(logs(n)) time
(i.e., a 32b value takes twice as long to process as a 16b value).

This is great for a "schoolbook" understanding of the algorithms
and an idea of how the "work" required varies with the input
value and/or range of supported values (i.e., an algorithm may
work well with a certain set of test values -- yet STUN the
developer when applied to *other* values).

But, when it comes to deciding which approach to use in a particular
application, you need to know what the "typical values" (and worst
case) to be processed are likely to be.  And, what the costs of the
operations required in each case (the various 'k' that have been
elided from the discussion).

If you're converting small numbers, the cost of a pair of counters
can be much less than the cost of a "machine" that knows how to
process a bit at a time.  So, while (in general) the counter approach
looks incredibly naive (stupid), it can, in fact be the best
approach in a particular set of conditions!

> BIG-O analysis allows you do do some testing at a data set size n1
> and then make a rough estimate of the run time for n2 > n1.
> this can be done for the hardware and processor instruction set.
> Its purpose is to avoid the naive estimate:
>  "I ran this on a data set of 100 and took 0.5 microseconds,
>   so on the production run of 1,000,000 it should only less
>   than a minute (50 seconds)."

If O(n), you'd expect it to be done in 5ms (0.5us*1,000,000/100).

By thinking in terms of HOW the algorithm experiences its costs,
you can better evaluate the types of operations (implementations)
you'd like to favor/avoid.  If you know that you are intending to
deploy on a target that has a particular set of characteristics
for its operations, you might opt for a different algorithm
to avoid the more expensive operators and exploit the cheaper ones.

Many years ago, I wrote a little piece of code to exhaustively
probe a state machine (with no buried state) to build a state
transition table empirically with only indirect observation
of the "next state" logic (i.e., by looking at the "current state"
and applying various input vectors and then tabulating the
resulting next state).

[This is actually a delightfully interesting problem to solve!
Hint:  once you've applied an input vector and clocked the machine,
you've accumulated knowledge of how that state handles that input
vector -- but, you're no longer in that original "current state".
And, you still have other input vectors to evaluate for it!]

How do you evaluate the efficacy of the algorithm that "walks"
the FSM?  How do you determine how long it will take to map
a FSM of a given maximum complexity (measured by number of
states and input vector size)?  All you know, /a priori/ is
the time that it takes to apply a set of inputs to the machine
and observe that *one* state transition...

[Exercise left for the reader.]

> Hopefully, folks here are not that naive to depend on just O(n).
> Your point is very important and worth repeating:
>  the analysis of algorithms can be more precise when it can
> take into account the features of the implementation environment.
> (I hope I phrased that close to what you meant.)

The more interesting cases are O(1), O(n^2), etc.  And, how to
downgrade the cost of an algorithm that *appears*, on its surface,
to be of a higher order than it actually needs to be.

> have a great day

Too late -- 119F today.

On 6/20/2017 3:07 PM, Ed Prochak wrote:

>>> have a great day
>>
>> Too late -- 119F today.
> 
> Wow, it cooled off a bit here, back to the 70's.
> Well try to stay cool.

Our highs aren't expected to fall below 110 for at least a week.
Night-time lows are 80+.

Hopefully this will pass before Monsoon starts (in a few weeks)