re-attaching arguments to features

[John Perry]

Hello everyone

I used to use Eiffel a lot about 15 years ago, but yesterday I had to implement some code for which I have samples in C++, Ada, Modula-2, etc. and I realized that Eiffel has matured a lot. That said, in one way I seem simply to have forgotten something, which leads to this question.

As I understand it, Eiffel is like Python in that a feature cannot re-assign or re-attach the value of an argument. That is, if a is an argument to feature f, then feature f cannot reassign a (i.e., attach another value to it, such as a := b). Put differently, Eiffel doesn't have "out" or "VAR" parameters the way Ada and the Pascal family does. The compiler refused to let me do anything like that last night, and after searching I found some statements that I thought were saying this.

Do I understand the situation correctly? (modulo terminology)

If not, how does pass an argument in a way that it can be re-attached?

If so, what is the "Eiffel way" to accomplish this?

One workaround I can see is to put argument a in a box b and pass that to f; then f can both extract and modify a. I encountered a performance hit from creating new boxes, but managed to avoid this using an expanded box (cut the runtime by more than 50%!).

I'm not sure I can always use expanded boxes, however, so I wondered if there was a better approach.

Thanks for any help you can give, and sorry if this is a stupid question.

john perry

[Colin Adams]

Your understanding is correct.

--
You received this message because you are subscribed to the Google Groups "Eiffel Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to eiffel-users...@googlegroups.com.
Visit this group at https://groups.google.com/group/eiffel-users.
For more options, visit https://groups.google.com/d/optout.

[Gerrit Leder]

Hi john,

Consider implementing a

- function with keyword result xor

- procedure p that sets a class attribute a

Have fun

Gerrit

Am Fr., 16. Nov. 2018, 17:55 hat Colin Adams <colinpa...@gmail.com> geschrieben:

[Larry Rix]

Hi John, 

 

You can also pass an object as an argument where the object has features and the features of that object can be attached or reattached. One simple way to do this without using an object is to pass a named Tuple and and then attach or reattach or a sign too the element of the Tuple.

 

Kind regards, 

Larry Rix

--

[r...@amalasoft.com]

If the argument is to be replaced in the procedure, then you can change the argument from type X to a CELL of type X.

replace_something_with_another_thing (tc: CELL [THING])

  do

    tc.put (some_other_thing)

  end

R

    

-------- Original Message --------
Subject: Re: [eiffel-users] re-attaching arguments to features
From: Colin Adams <colinpa...@gmail.com>
Date: Fri, November 16, 2018 11:55 am
To: eiffel...@googlegroups.com

Your understanding is correct.

[Finnian Reilly]

For string arguments you can use the `share' routine to change the value of the string.

For numeric arguments you can use the X_REF form where X is a numeric type, INTEGER_REF for example. Use routine `set_item' to change the value.

[Larry Rix]

Yep-- that is another way. The idea is that while the object reference itself cannot be changed, a reference within it can. Be it CELL or TUPLE or some other object you create and pass, the setup is the same. CELL is a great way to do it.

[John Perry]

I've not heard of the CELL thing; that looks new, but maybe I was unaware of it before. The big question for me is, is it *efficient*? I will try it later.

I think Larry Rix's idea is essentially what I ended up doing, though I didn't use a TUPLE. I will probably try that, too.

I had tried Gerritt's idea, but I used a tuple, and I kept hitting a compiler error where it insisted that I was returning a shared detachable, which I could not attach to a plain detachable. (This is from memory, so I might be saying it wrong.)

My only real concern now (aside from trying CELL and TUPLE) is that the current version is only about 2x slower than the Ada & C++ versions, which is still better than the 10x slower that I started with. It's clear however that the main slowdown is that I have to load up these objects with the data, then retrieve them after the fact.

Thanks to everyone for the replies! It's clear that my understanding is correct, and it looks as if most people suggested something along the lines of what I ended up doing.

[Peter Gummer]

John Perry <john....@usm.edu> wrote:

I've not heard of the CELL thing; that looks new, but maybe I was unaware of it before.

I remember CELL from more than 15 years ago, John, and I think it was being used in code that was already quite old back then. It was common to see it used as the result type of once functions.

CELL is documented at https://www.eiffel.org/doc/solutions/EiffelBase_Data_Structures%2C_Lists as a cell containing data in a linked list. It’s mentioned again in regard to linked lists in Meyer’s OOSC2, which dates from the mid-90s.

With such a long pedigree, hopefully it’s been well optimised!

Peter

[John Perry]

On Friday, November 16, 2018 at 5:18:22 PM UTC-6, Peter Gummer wrote:

John Perry <john....@usm.edu> wrote:

I've not heard of the CELL thing; that looks new, but maybe I was unaware of it before.

I remember CELL from more than 15 years ago, John, and I think it was being used in code that was already quite old back then. It was common to see it used as the result type of once functions.

Interesting. Was it in the SmartEiffel libraries? That's what I used back then. I just checked its website (still around!) and opened up the "All Classes" tab in their library reference. It doesn't seem to have a CELL class.

 

With such a long pedigree, hopefully it’s been well optimised!

I did try compiling with CELL and/or TUPLE, but in each case I kept bumping up against the following problems:

  -- the parameter has to be initialized, which involves copying data, the very problem I'm having when I use a specialized class;

  -- in some cases the compiler tells me I'm trying to attach "shared detachable ANY" to a "shared detachable T".

So far I've successfully tried returning the modified values as a result, and using a class feature of a specialized type to store intermediate results. None of these gets me faster than 4-5x slower than C++ code, and I'm reasonably sure it's because of all the copying that this forces me to do. (Earlier I had said 2x slower but it turned out I hadn't noticed a bug; fixing it got me back to 5x slower. That's still better than 10x slower, but...)

john perry

[Larry Rix]

I find that it is best to use a "named TUPLE" when passing a TUPLE. You can just pass a plain TUPLE and then access the items like an array, but (to me) the code is difficult to read and there are no real semantics because one does not have names.

The thing to know about CELL is—first—it is a class. Second—it is designed to hold a single object of type ANY (I am shooting from the hip here). The nice thing is that it is light weight. It's limit is that it can contain but one object and not many, which is the advantage of TUPLE (especially a named TUPLE to get the semantics).

Cheers,

Larry

[John Perry]

Everyone's tried to be helpful but the more I try to use CELL and TUPLE the more I don't see how they're actually helpful in my case -- efficiency being a prime concern. So I thought I'd show comparable Ada code, along with my current Eiffel code, & see if anyone can lift the fog from my mind.

Here's the Ada code:

procedure split(orig: NodePtr; lower, greaterOrEqual: in out NodePtr; val: Integer) is

begin

  if orig = null then

    lower := null;

    greaterOrEqual := null;

    return;

  end if;

  if orig.x < val then

    lower := orig;

    split(lower.right, lower.right, greaterOrEqual, val);

  else

    greaterOrEqual := orig;

    split(greaterOrEqual.left, lower, greaterOrEqual.left, val);

  end if;

end split;

For those unfamiliar with Ada, "in out" means that data comes in and goes out of lower and greaterOrEqual. What I find challenging is that it's recursive, so having just one cell or tuple won't do. I either create a new one with each recursive invocation, or I copy the data particular to this invocation, put new data in, etc.

That's more or less what my current Eiffel version does:

split(orig: detachable NODE; val: INTEGER)

local

lower, greater: NODE

do

if orig = Void then

subnodes2.lower := Void

subnodes2.greater_equal := Void

elseif orig.x < val then

lower := orig

subnodes2.lower := lower.right

split(lower.right, val)

lower.right := subnodes2.lower

subnodes2.lower := lower

else

greater := orig

subnodes2.greater_equal := greater.left

split(greater.left, val)

greater.left := subnodes2.greater_equal

subnodes2.greater_equal := greater

end

end

Here, "subnodes2" stores the data that needs to be passed & modified. In order to invoke it recursively, I have to store its data in temporary variables, and all that copying around incurs a time cost.

Would using CELL or TUPLE fix that? If so, can I get a hint? ;-)

(I think that in my SmartEiffel days I just re-thought the code, but for various reasons that isn't an option in this case.)

[Eric Bezault]

Hi John,

I think that MEMO was the equivalent of CELL in SmartEiffel.

> Everyone's tried to be helpful but the more I try to use CELL and TUPLE
> the more I don't see how they're actually helpful in my case --
> efficiency being a prime concern. So I thought I'd show comparable Ada
> code, along with my current Eiffel code, & see if anyone can lift the
> fog from my mind.

In my opinion I think that it is a mistake to try to literally
translate a program written in language X to another language Y
and try to emulate what is not supported in this latter language.

An Eiffel programmer would not implement `split' with recursive
calls (probably because Eiffel does not support in/out arguments).
Instead of that, he or she would implement `split' using a loop.

So if performance is your concern, I would recommend that you
write Eiffel code while keeping in mind what Eiffel can do best
for you, instead of writing Ada code with Eiffel's syntax.

--
Eric Bezault
mailto:er...@gobosoft.com
http://www.gobosoft.com

[r...@amalasoft.com]

Hi John

With all the good suggestions from everyone, we seem to have lost sight of a fundamental principle of design - query/command separation.  We're looking to create a deliberate side-effect and that is not good thing.

It strikes me that a better approach is to create a function (not a procedure) that returns the replaced or converted object, or a value related to it.  The result would simply be assigned to the original handle at the caller.  Such an arrangement could be recursive if so desired.

This approach might involve object creation, but if the work being done in the function is a kind of analysis, getting indices within a longer string, for example, the result type could be a TUPLE or ARRAY of indices, and only the final operation, at the original caller, would involve object creation (with a substring-like operation, for example).

A more precise description of the _intent_ of your procedure, rather than just the _content_ of it would give these helpful folks a better chance of offering a fully relevant solution.

R

-------- Original Message --------
Subject: [eiffel-users] Re: re-attaching arguments to features
From: John Perry <john....@usm.edu>
Date: Fri, November 16, 2018 7:39 pm
To: Eiffel Users <eiffel...@googlegroups.com>

Everyone's tried to be helpful but the more I try to use CELL and TUPLE the more I don't see how they're actually helpful in my case -- efficiency being a prime concern. So I thought I'd show comparable Ada code, along with my current Eiffel code, & see if anyone can lift the fog from my mind.

[John Perry]

For those who want to know, the overall project builds a tree using recursive merge, then searches for elements, or erases them, by recursive split, followed by recursive merge. The task is actually a challenge to implement this algorithm/approach as efficiently as possible in different languages, so I am under the impression that I have to implement the recursive approach.

I don't actually like the recursive approach, so I'll inquire about that. I've implemented trees before, and I would use loops, but once I got into it, it became something of a challenge to figure out how to modify an argument, if possible.

Thanks to everyone for for the help.

(The original code was C++ anyway; I just can't stand reproducing C++ if I can help it ;-) so I included an Ada transliteration -- I'd like to think that Ada users wouldn't ordinarily use recursion, either. Probably not most C++ users for that matter. I am sort of perplexed why it was done this way.)

[John Perry]

While reviewing the issue, I noticed that in some languages used to implement this algorithm (e.g., Haskell) tinkering with garbage collector parameters led to a huge speedup in timing. Similarly, the Modula-3 implementation's time decreases by 50% when one switches from traced references to unsafe pointers, so now I'm wondering if Eiffel's garbage collector is a significant part of the penalty.

And this is the task's website:

    github.com/frol/completely-unscientific-benchmarks

Inasmuch as it's "completely unscientific" I'm not taking it that seriously; I was, again, more interested in how to pursue this particular construct in Eiffel.

john perry

[r...@amalasoft.com]

Hi John

It does have an impact, and you can control it.  You might recall that the MEMORY class provides features to control GC.

For this kind of exercise, disabling collection certainly won't hurt things, and will eliminate its effect.

R

-------- Original Message --------
Subject: Re: [eiffel-users] Re: re-attaching arguments to features
From: John Perry <john....@usm.edu>

--

[John Perry]

Hi R

I tried to disable it via collection_off, and also tried using free(), all without significant effect.

I did try rewriting one procedure (not the ones given here) as a loop, instead of recursive. The difference was huge: a 33% reduction in time, with the output still correct this time :-)

I'll talk to the organizer about using loops instead of recursion.

regards

john perry

[Eric Bezault]

Hi John,

> I did try rewriting one procedure (not the ones given here) as a loop,
> instead of recursive. The difference was huge: a 33% reduction in time,
> with the output still correct this time :-)
>
> I'll talk to the organizer about using loops instead of recursion.

If recursivity is really required, I would suggest passing the
parent node of lower and the parent node of greater_or_equal
in place of the in/out arguments. For the initial call you pass
empty nodes, and you can retrieve the lower on the right of
the first node, and greater_or_equal on the left of the second
node. Something like that:

split (orig: detachable NODE; parent_of_lower,
parent_of_greater_or_equal: NODE; val: INTEGER)

do
if orig = Void then

parent_of_lower.set_right (Void)
parent_of_greater_or_equal.set_left (Void)
elseif orig.x < val then
parent_of_lower.set_right (orig)
split (orig.right, orig, parent_of_greater_or_equal, val)
else
parent_of_greater_or_equal.set_left (orig)
split (orig.left, parent_of_lower, orig, val)
end
end

do_split (orig: detachable NODE; val: INTEGER): TUPLE [lower,
greater_than_or_equal: detachable NODE]
local
parent_of_lower, parent_of_greater_than_or_equal: NODE
do
create parent_of_lower
create parent_of_greater_than_or_equal
split (orig, parent_of_lower,
parent_of_greater_than_or_equal, val)
Result := [parent_of_lower.right,
parent_of_greater_than_or_equal.left]
end

Note that this is pseudo code: I didn't try to compile it and
run it to see if it does what it is supposed to do. It's just
to give you an idea. I also let as an exercise the addition of
the proper assertions to these routines.

For performance/executable size/etc., you could try compiling your
solution with the Gobo Eiffel compiler.

[John Perry]

Eric

It turns out that this idea helped a lot. It required a bit more detail than this -- I really had to study the algorithm -- but it cut the running time by ~33% on my machine -- finally something significant! That's still quite a bit slower than most other compiled languages, but at this point I'm putting more effort into it than warranted, and the individual in charge of the project does want the recursion preserved. Barring something unexpected, I think I will leave it as is.

You mentioned the gobo eiffel compiler. I've seen it before, and I know it's your work. Are you saying that it is likely to be more efficient on certain things than Eiffel.com's compiler achieves with finalized code?

Also, its webpage indicates that a lot of Eiffel's features are not implemented, but to be honest I remember looking at it years ago and it looks like it's exactly the same list as it was then. Is it any more up-to-date.

john perry

[John Perry]

Oops. I should qualify something.

it cut the running time by ~33% on my machine -- finally something significant! That's still quite a bit slower than most other compiled languages...

I mean, it's "quite a bit slower than most other compiled languages I've actually tried from that project" (Nim, Oberon, Modula-2, Modula-3, Ada, C++, with Java & similar languages being slower). I don't know about some others.

john perry

[Peter Gummer]

Hi John,

If “Java and similar languages” are slower, then maybe it’s garbage collection that’s slowing them down. The other languages don’t have GC as far as I know. Have you had the opportunity to try switching GC off in your Eiffel version?

Peter

[Eric Bezault]

Hi John,

> You mentioned the gobo eiffel compiler. I've seen it before, and I know
> it's your work. Are you saying that it is likely to be more efficient on
> certain things than Eiffel.com's compiler achieves with finalized code?
>
> Also, its webpage indicates that a lot of Eiffel's features are not
> implemented, but to be honest I remember looking at it years ago and it
> looks like it's exactly the same list as it was then. Is it any more
> up-to-date.

I think that this list:

http://www.gobosoft.com/eiffel/gobo/gec/limitations.html

is pretty accurate. Note that other Eiffel compilers might have other
limitations, even if they are not made as visible as in this page.
You said that a lot of Eiffel's features are not implemented. To be
honest, I think that this list is pretty small compared to all the
other Eiffel's features which are implemented. And for your project
you should not be impacted by what is not implemented (otherwise
I would have not suggested that you could try it).

For your project, what is interesting with Gobo is that:

* It produces much smaller executables when your project is small
(no huge run-time of stuff not used in small programs).

* No GC by default. Note that this is better than having a GC
which is turned off because even though no GC cycle is triggered,
the GC still keeps track of the objects being created.

* Less overhead on each feature call. This is important if your
recursive calls are deep. Because of the moving GC of EiffelStudio,
there is an overhead at the beginning of each feature call in
order to register the local variables and arguments.

* The Gobo compiler does some static analysis of the dynamic type
set of each entity in the Eiffel program, which makes it possible
to better optimize polymorphic calls if the dynamic type set
of the target of the call contains only one type.

* Thanks the dynamic type sets computed above, the Gobo compiler
can also report possible CAT-calls at compilation time. But this
is less relevant for you because it does not bring any improvement
in speed or executable size.

One last thing to get better speed is too make sure that the
setting 'exception_trace' is turned off in your ECF file
(this is the default in ECF, but EiffelStudio might turn it
on during the development stage).

Note that the Gobo compiler can compile itself and produces an
executable that is smaller and runs faster than when compiled
with EiffelStudio. With that respect, it has benchmarks similar
to what we used to have with SmartEiffel. But the big improvement
over SmartEiffel is that it is fully compatible with EiffelStudio.
It even uses the same kernel library. This means that you can
do your development, debugging, etc. with the nice IDE of
EiffelStudio, and decide to compile with the Gobo compiler
(or not) at the end of development in case it produces a better
executable (or not) for what you want to achieve.

If you decide to give it a try and need some help with it, you
can either contact me directly or use Gobo mailing list.

[John Perry]

Peter

If “Java and similar languages” are slower, then maybe it’s garbage collection that’s slowing them down. The other languages don’t have GC as far as I know. Have you had the opportunity to try switching GC off in your Eiffel version?

I realized later that that statement might burn me, because I didn't say "slower than" whatever. In fact, I haven't looked at the Java version, or even tested its time against Eiffel; I just know that they're quite a bit slower from the project's main page.

I should note that the repository maintainer has pointed out that the initial submission should be a "naive" implementation that someone who knows enough about the language would implement for correctness, but not efficiency. He already seems perturbed that I revised my implementation to improve its performance; I've pointed out that it was because I'm really rusty with Eiffel, and the technique was suggested by someone who uses it all the time (I hope that's an accurate description of Eric :-)).

For what it's worth, though, I did try "allocate_fast" and "collection_off" for the sake of a tuned version. The former had a positive effect; the latter seemed to have a negative one, believe it or not -- perhaps because of the relatively short running time. My half-educated guess is that the bottleneck currently involves (a) all the checks for void safety, and (b) all the copying I have to do to get around the language constraints.

I'd like to discard the checks for void-safety, but Eiffel doesn't seem to have a way to tell the compiler that I *know* this object will be non-Void at a certain time. That's probably a good thing in general -- Kotlin's !! operator has burned me a few times ;-) -- but it does mean I have to put in "if attached... as..." in lots of places where I know from the logic that it wouldn't be there unless the object were non-void. (If this is where someone tells me Eiffel does have such a construction, all the better!)

Speaking of tuning, I did try the EiffelStudio profiler, but the results it gave were not really helpful, and I thought it odd that the % of time spent in a couple of functions was along the lines of 250% and 500%, but that's probably where RTFM comes into play.

john perry

[Eric Bezault]

On 19/11/2018 15:56, John Perry wrote:
> I should note that the repository maintainer has pointed out that the
> initial submission should be a "naive" implementation that someone who
> knows enough about the language would implement for correctness, but not
> efficiency. He already seems perturbed that I revised my implementation
> to improve its performance; I've pointed out that it was because I'm
> really rusty with Eiffel, and the technique was suggested by someone who
> uses it all the time (I hope that's an accurate description of Eric :-)).

Surely my "naive" implementation of this program in C# would not look
the same as the "naive" implementation made by someone who uses C# every
day!

Also, the "naive" implementation in Eiffel would use loop, not
recursion. So what is asked (naive + recursion) does not exist
in Eiffel.

If recursion is needed, then, since we cannot modify the values
passed as arguments, passing their enclosing objects (the
objects containing the values that we want to modify) is the
way I would implement it in Eiffel. So this is the way I would
implement it (naive or not), without the seek of speed. This is
different from tuning the GC or trying to use other compilation
options to improve speed. This is not naive and even me I
don't do that in the Eiffel programs that I write every day.