Container library (continued)

[jacob navia]

Gareth Owen a écrit :

Thanks for your full answers, Jacob. Very informative.
Just a couple of quick comments
i) An explicit copy, plus inplace sort() is probably better than an
auto-copying sort. It's more flexible.

I think you are right. But if I change this for the string collection I have
to change Sort for all containers...

But I think you are right basically. An auto-copying interface would be
difficult for big containers.

I will change Sort to be

bool Sort(some_container); // Returns whether Sort succeeded or not

If you want to keep the non-sorted container you copy it before.

Also, if you have a huge

array, you don't want to require twice as much memory.

Yes, that is the point I missed. Thanks.

ii) What happens if the auto-copying sort runs out of memory? I know
lcc-win has exceptions, and those without can call a user specified
function, but is that function responsible for cleanup, or does the
Sort() routine do this itself?
What happens to control flow, does Sort() return NULL?

``
With the changed interface you receive a boolean indicating success/failure.
If there is no memory, a user defined error function is called. The default
function provided by the library prints a message to stdout and aborts.
But you can define an error function of your own. If that function returns
Sort returns false.

Thanks for your input.

 

[David Thompson]

Let's speak with an example: [1]

To transform a year with 4 digits (i.e. YYYY format) into a number, you
call in Java the atoi equivalent DecimalFormat.Parse()

(Nit: .parse is lowercase; Java like C is case-sensitive.)

That's not 'equivalent' to atoi. DecimalFormat is much closer to COBOL
(or PL/I) PICture editing, or a bit above C *printf/scanf + locale
stuff. The paper you cite basically says so:

The first five transformations come from the general purpose
DecimalFormat class. It can parse or format any kind of decimal
number. SimpleDateFormat, however, uses it for a special case, to
parse integer months, days, and years. The first, fifth, and sixth
transformations are necessary only because of this overgenerality.

The much closer analog to atoi is Integer.parseInt, which uses no
extra objects, not even a box. (Sounds timely for Xmas!) Or the nearly
identical Long.parseLong, which is what DigitList.getLong actually
uses, and the paper counts as one call -- although both the Integer
and Long versions actually (are coded to) call String.charAt and
Character.digit for each digit, but I'd bet these java.lang basics are
practically guaranteed to get JITted.

In abstract Short.parseShort (16bit) is enough for 4 decimal; but
(as of the version I have installed, 6usomething) it just delegates to
Integer.parseInt plus a range check. Presumably on the theory, as in
C, that int is the 'natural' size (even though Java fixes it at 32bit)
and there's usually no savings to doing anything narrower.

This is a VERY general routine, that

(1) takes each digits and builds a LIST of digits. It builds a list
container object.

(As of 6uwhatever) it's actually a wrapped (hidden) array of char.
But it is another object, and used (accessed) as a list.

(2) Then, it copies the digits into a StringBuffer object.

(3) Then it copies the buffer into a String object.

True -- and particularly silly, since String can be constructed
directly from array of char; and the Sun doc prefers StringBuilder
when threadsafety isn't needed, and here it isn't; and finally parsing
could as well be defined on array of char in the first place.

(4) Then, it parses the string and produces a 64 bit long result.

Cost: 4 calls, 3 objects, 600 instructions (!!!)

Just browsing and not counting exactly, I would estimate a somewhat
smaller instruction count, but not hugely so.

THEN,

It "boxes" the value into a boxed long, that needs to be
unboxed to yield (at last) the int that the user is expecting.

We have in total 11 calls and 5 temporary objects created.

If executed as bytecode. If JITted, possibly some temporaries can be
eliminated using context. Of course, using the right routine in the
first place avoids the need for clever (and possibly costly)
optimization. Which should not be a big surprise.

[1]
http://domino.research.ibm.com/comm...ges/nickmitchell.pubs.html/$FILE/lcsd2005.pdf