Re: Regression testing for pointers

From	Don Y <this@isnotme.com>
Newsgroups	comp.lang.c
Subject	Re: Regression testing for pointers
Date	2012-03-13 10:19 -0700
Organization	Aioe.org NNTP Server
Message-ID	<jjnvii$e7d$1@speranza.aioe.org> (permalink)
References	(11 earlier) <9s80hcFhvvU1@mid.individual.net> <jjmser$jnv$1@speranza.aioe.org> <9s8bjmFhvvU5@mid.individual.net> <jjmurk$ohs$1@speranza.aioe.org> <9s8ee6FhvvU6@mid.individual.net>

Show all headers | View raw

Hi Ian,

>>> Your typical memory allocator is a little more complex and less
>>> deterministic than strchr().
>>
>> But it still produces *a* result. It is a deterministic
>> algorithm (even if the specification -- like malloc -- doesn't
>> make that determinism explicit). With a given set of operating
>> conditions and inputs, you **KNOW** what the result will be.
>> TEST FOR THAT RESULT!
>
> It may produce a result, but more often than not, the exact value is of
> little on no consequence.

Is the exact value of sqrt()'s result of no consequence?

> If you start to test for specific values based
> on knowledge of the internals, you end up with a very fragile test

No!  I am *not* looking at test internals.  I am looking at
the SPECIFIED, CONTRACTUAL BEHAVIOR of the function.  Are
you "looking at internals" when you test the return value
of sqrt(5)?  The sqrt function returns a positive value
for all non negative arguments such that the value, when
multiplied by itself, yields the original argument.  THAT
is what you test for!

A *good* test picks values that are likely to cause problems
in an implementation and.or *this* implementation.

A memory allocator is no different.  Pretend the "addresses"
returned were integers and the specification was written in
terms of *integers*.  You wouldn't throw an arbitrary input
value at it and not *carefully* examine the result to see that
it complies with EXACTLY what you would expect, given its
contract.

And, if your goal was to ensure that the function behaved well
in the wide variety of cases that it might be subjected to
once deployed, you would think very carefully about *which*
conditions you put it in and how you exercised them.

If you developed a general purpose (4 function) calculator,
would you use 1+1, 8-5, 3*4, etc. as your test cases?  Or,
would you think:  "Hmmm... I wonder if it handles negative
arguments properly?  And negative *results*?  And, what happens
if I give it something too big -- 99999999+1?  Or, something
'undefined' -- 345/0?"

"Settling" for what the linker gives you as the location for
the heap (as well as its *size*!) means you will *never* test
the code with any degree of confidence GIVEN THAT IT WILL
BE DEPLOYED IN ENVIRONMENTS OTHER THAN YOURS!

How do you test sqrt?  Don't *you* pick the values that are
of interest to you in proving correct operation of the
function?  Don't *you* verify that the results are "as
expected"?

Granted, for an invertible function you could potentially do
a monte carlo simulation having the test suite check the
results (i.e., if result*result =~ argument, then pass).
How would you apply that "random" approach to testing a
non-invertible function?  Or, one who's inverse function
is of a complexity greater than or equal to the original
function (e.g., a secure hash)?

> harness. I think this may have been what you were saying elsewhere. If
> your tests become bonded to single implementation, you are stuck with
> it. If your tests don't assume specific values, you are free to change

If your tests don't assume specific values, then you can't guarantee
where in the function's *domain* you are testing.

> the internals of the function as long as you don't break its published
> behaviour. Obviously if your internal implementation is specified you
> are stuck.

The internal implementation need not be "fixed".  You are still
free to implement the function however you want -- as long as
the external interface and the guarantees that it affords the
developer are ALWAYS met.

> Memory allocators are definitely one of those cases where one size does
> not fit all, just look at the range of malloc libraries available for a
> typical non-embedded environment. They would all pass the same test
> suite assuming the tests didn't make assumptions about the implementation.

No.  It would be easier for *your* "implementation agnostic" approach
to test *all* of those allocators with a given test suite. Because
you don't *know/care* how they are making their choices!  "Did I
get a result?  OK.  Does it overlap any other results I have had?
No.  Does the chunk returned fit entirely in the *stated* (by
the linker!) area of the heap?  Yes.  Lather, rinse, repeat."

>>> I thought you were test a general purpose allocator.
>>>
>>> If your requirements are that specific, what's wrong with
>>>
>>> ASSERT(result == heapBase+0x32440)?
>>
>> What happens if heapBase is effectively (char *) -32400?
>> What happens if the processor only has a 16b address space?
>> What happens if that +32440 was a consequence of pointer
>> alignment requirements on THIS PLATFORM?
>> What happens if there isn't physical memory present at
>> that location?
>
> You break 0x32440 down into platform independent variables.

And how is that any different from platform *dependent*
variables?  You still need to "tune" the values to fit
the *particular* (test) deployment.  And, you have no
guarantee that you are poking around all the right
"dark corners" for the routine -- since you are not in
control of the conditions that your function is being
subjected to!

>> If I know where (on this particular platform) the heap is located
>> and how large it is and alignment constraints, etc. AND have just
>> initialized the heap... THEN:
>> - I know what the internal free list looks like, "conceptually"
>> (I might not know specific bit patterns but I know what the
>> free list *reflects* -- a heap that is completely FULL!
>> - given that free list, I know how any particular allocation
>> request WILL be handled.
>> - given how that request is handled, I now know what the NEW
>> state of the free list will be.
>> - lather, rinse, repeat
>
> Until someone introduces a critical optimisation that changes the layout...

Until someone changes what "sqrt" means!

I *only* -- though THOROUGHLY -- test *published*, contractual
guarantees that the function *must* honor.  What goes on under the
hood is never examined, directly.

You can implement sqrt with Newton-Rhapson, large lookup tables,
CORDIC, etc.  Your test suite DOESN'T CARE!  As long as sqrt(foo)
truly produces the square root of foo!

I can change the internals of the memory allocator any way I choose
AS LONG AS the results returned for a given set of operating
conditions and input variables REMAIN UNCHANGED.

E.g., the allocator makes no claims about the *content* of the
blocks of memory allocated.  I could add some code to zero them
out, fill them with pseudo-random numbers -- or just leave
their previous contents "as is".  The test suite can't *test*
any of those conditions because none are guaranteed in the
contract.  If I find it more efficient to leave assorted
crap *in* the chunks, the test suite can't complain!

(If K&R's malloc wants to do a "first fit" selection strategy,
there's nothing preventing it!  Nor anything preventing it
from changing that, in a later edition, to a "last fit".
The test suite for *their* malloc would have to accept both
sets of results as equally valid.)

> I still think you are testing at too high a level, test the functions
> that manipulate your internal independently.

There *is* nothing else.  the allocator and the deallocator
are the *only* things that massage the internal state of the
heap!

Thread

Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-09 16:43 -0700
  Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 12:56 +1300
    Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-09 19:40 -0700
      Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 17:53 +1300
        Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 18:12 +1300
        Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 02:05 -0700
          Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 23:17 +1300
            Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-10 12:00 +0000
              Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 11:00 +1300
                Re: Regression testing for pointers Ike Naar <ike@iceland.freeshell.org> - 2012-03-10 22:23 +0000
                Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-10 22:40 +0000
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 12:12 +1300
                Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-11 00:42 +0000
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 14:26 +1300
                Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-11 03:09 +0000
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 18:16 +1300
            Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 12:01 -0700
              Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 10:35 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 09:19 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 07:23 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:23 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:25 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 00:19 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 20:34 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 01:00 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 21:22 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 10:19 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 07:25 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 02:00 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 22:18 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 11:32 -0700
                Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-15 05:58 -0700
                Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-15 05:55 -0700
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-15 11:32 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-16 18:14 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-20 01:43 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-20 21:59 +1300
                Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-16 03:05 -0700
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-20 02:33 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-24 11:49 +1300
          Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 05:01 -0700
            Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 09:44 -0700
              Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-12 09:56 +1300
    Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-10 02:28 -0800
      Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 11:09 -0700
      Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-10 18:29 +0000
        Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 05:22 -0700
          Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 09:50 -0700
            Re: Regression testing for pointers "io_x" <a@b.c.invalid> - 2012-03-13 13:09 +0100
  Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-10 03:14 +0000
    Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 12:42 -0700
  Re: Regression testing for pointers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-10 08:42 +0000
    Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 02:19 -0700
      Re: Regression testing for pointers "BartC" <bc@freeuk.com> - 2012-03-10 15:54 +0000
        Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 11:49 -0700
          Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 06:09 -0700
            Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 12:33 -0700
              Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-12 03:29 -0700
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 10:01 -0700
                Re: Regression testing for pointers "BartC" <bc@freeuk.com> - 2012-03-13 18:56 +0000
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 16:31 -0700
      Re: Regression testing for pointers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-12 00:30 +0000
        Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:41 -0700
      Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-12 13:39 +1300
        Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 09:36 -0700
          Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 07:25 +1300
            Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:28 -0700
              Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-13 04:20 +0000
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:34 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 00:29 -0700
              Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:31 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 01:05 -0700
                Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 21:30 +1300
                Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 10:43 -0700
  Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-10 15:41 -0800
    Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 11:23 -0700
      Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-13 13:43 -0700
        Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 01:45 -0700
          Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-14 15:15 -0700
            Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-14 22:57 +0000
              Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-15 13:10 -0700
                Re: Regression testing for pointers jgk@panix.com (Joe keane) - 2012-03-16 22:20 +0000
                Re: Regression testing for pointers "io_x" <a@b.c.invalid> - 2012-03-18 07:15 +0100
            Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 23:13 -0700
  Re: Regression testing for pointers gordonb.b29ri@burditt.org (Gordon Burditt) - 2012-03-12 19:37 -0500
    Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 19:23 -0700
  Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 13:12 +1300
    Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 01:54 -0700
      Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 22:05 +1300
        Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 11:54 -0700

csiph-web