Ruby: politics & performance [long]

ruby-talk
21

Hi,

···

In message “Re: Ruby: politics & performance [long]” on 03/01/13, ts decoux@moulon.inra.fr writes:

Not the second word, the second element. For example actually you have

last = list;
while (last->nd_next) {
last = last->nd_next;
}

Try to replace it with

if (list->nd_next) {
last = list->nd_next->nd_end;
}
else {
last = list;
}

i.e. the first element give the size, the second give the end.

You just need to adapt one macro in eval.c to make it work (if I’m right)

This is interesting. I will try this in 1.8.0.

						matz.
22

Bulat Ziganshin wrote:

can you auto-split generated program into several files? this must

help with g++

Yes, I tried something like that. I had to split the C++ main()
function into sections some time ago to keep ld happy, but
the file grew too big for g++. I didn’t want to split it into
different files.

With Ruby, I tried putting delimiter lines (#===) at intervals in
the file and then piping the file one section at a time to a
Ruby subprocess. That helped a little, but not much: The real
problem isn’t the long file, it’s the long lists of arguments that
make up the arrays.

Louis

23

like there were any oversize problems already, huh?

···

On Tue, Jan 14, 2003 at 03:37:20AM +0900, Harry Ohlsen wrote:

you could generate XML

–
---- WBR, Michael Shigorin mike@altlinux.ru
------ Linux.Kiev http://www.linux.kiev.ua/

24

Louis Krupp lkrupp@pssw.NOSPAMPLEASE.com.invalid writes:

Phil Tomson wrote:

In article 200301111701.12221.transami@transami.net,

one option might be to use hashes in place of arrays. you can index
them yourself. instead of [a, b, c] use {0=>a, 1=>b, 2=>c}. hashes,
i was suprised to discover, are around 12x faster than arrays.
except that he’s talking about list_append as used in the
parser… I don’t think using hashes will help at all. It seems
that the issue has to do with node lists which are constructed by
the parser.

Correct – I think it’s this bit of parse.y:

args : arg
{
value_expr($1);
$$ = NEW_LIST($1);
}
> args ‘,’ arg
{
value_expr($3);
$$ = list_append($1, $3);
}
;

For the first item in the list, list_append has to check one
node, for the second it looks at two, and
1 + 2 + 3 + … + n = (n**2 + n)/2 traversals for n items.

list_concat does basically the same thing.

In that case, a simple fix would be one extra indirection, assuming
list_reverse and list_prepend are available:

args1 : args { $$ = list_reverse($1); }

args : arg
{
value_expr($1);
$$ = NEW_LIST($1);
}
> args ‘,’ arg
{
value_expr($3);
$$ = list_prepend($1, $3); /* was list_append */
}
;

For any given argument list, this would reduce effort to O(n)…

···

Tom Sawyer transami@transami.net wrote:

25

This is interesting. I will try this in 1.8.0.

Something like this (not fully tested)

diff -u ../ruby/eval.c ruby/eval.c
--- ../ruby/eval.c 2003-01-09 13:51:27.000000000 +0100
+++ ruby/eval.c 2003-01-13 12:45:19.000000000 +0100
@@ -1796,14 +1796,14 @@
# define TMP_ALLOC(n) ALLOCA_N(VALUE,n)
#endif

-#define SETUP_ARGS(anode) do {\
+#define SETUP_ARGS0(anode, alen) do {\
     NODE *n = anode;\
     if (!n) {\
        argc = 0;\
        argv = 0;\
     }\
     else if (nd_type(n) == NODE_ARRAY) {\
- argc=n->nd_alen;\
+ argc=alen;\
         if (argc > 0) {\
             int i;\
            n = anode;\
@@ -1828,6 +1828,16 @@
     }\
} while (0)

+#define SETUP_ARGS(anode) do {\
+ if (anode) {\
+ SETUP_ARGS0(anode, anode->nd_alen);\
+ }\
+ else {\
+ argc = 0;\
+ argv = 0;\
+ }\
+} while (0)

···

+
#define BEGIN_CALLARGS do {\
     struct BLOCK *tmp_block = ruby_block;\
     if (ruby_iter->iter == ITER_PRE) {\
@@ -2854,7 +2864,7 @@

            recv = rb_eval(self, node->nd_recv);
            rval = node->nd_args->nd_head;
- SETUP_ARGS(node->nd_args->nd_next);
+ SETUP_ARGS0(node->nd_args->nd_next, node->nd_args->nd_alen - 1);
            val = rb_funcall2(recv, aref, argc-1, argv);
            switch (node->nd_mid) {
            case 0: /* OR */
diff -u ../ruby/parse.y ruby/parse.y
--- ../ruby/parse.y 2003-01-09 13:52:01.000000000 +0100
+++ ruby/parse.y 2003-01-13 14:22:19.000000000 +0100
@@ -4498,16 +4498,18 @@
list_append(list, item)
     NODE *list, *item;
{
- NODE *last;
-
- if (list == 0) return NEW_LIST(item);
+ NODE *last, *node;

- last = list;
- while (last->nd_next) {
- last = last->nd_next;
+ node = NEW_LIST(item);
+ if (list == 0) return node;
+ if (list->nd_next) {
+ last = list->nd_next->nd_end;
     }
-
- last->nd_next = NEW_LIST(item);
+ else {
+ last = list;
+ }
+ last->nd_next = node;
+ list->nd_next->nd_end = node;
     list->nd_alen += 1;
     return list;
}
@@ -4519,14 +4521,20 @@
{
     NODE *last;

- last = head;
- while (last->nd_next) {
- last = last->nd_next;
+ if (head->nd_next) {
+ last = head->nd_next->nd_end;
+ }
+ else {
+ last = head;
     }
-
     last->nd_next = tail;
     head->nd_alen += tail->nd_alen;
-
+ if (tail->nd_next) {
+ head->nd_next->nd_end = tail->nd_next->nd_end;
+ }
+ else {
+ head->nd_next->nd_end = tail;
+ }
     return head;
}

@@ -4544,6 +4552,7 @@
     if (htype == NODE_EVSTR) {
        NODE *node = NEW_DSTR(rb_str_new(0, 0));
        node->nd_next = NEW_LIST(head);
+ node->nd_next->nd_end = node->nd_next;
        node->nd_alen += 1;
        head = node;
     }

Guy Decoux

26

I did say it was just an example :-).

In my case, XML is very helpful, because we’re using XSLT to perform a lot of
transformations that would be a right pain to do using custom-built code.
XML is definitely not the panacea that people would lead you to believe, of
course. It just happens to work well in some cases, though.

All I was getting at was that with a bit more information, one of the people
on the list might see a completely different way to solve the problem, that
didn’t involve generating the huge arrays in the first place.

That’s not to say there is such a solution, but it’s easy to become blinkered
when you’ve put a lot of effort into going down one path. A fresh
perspective can often be very helpful.

H.

···

On Tue, 14 Jan 2003 06:07, Michael Shigorin wrote:

On Tue, Jan 14, 2003 at 03:37:20AM +0900, Harry Ohlsen wrote:

you could generate XML

like there were any oversize problems already, huh?

27

In article 1042469883.310827.25295.nullmailer@picachu.netlab.jp,

···

Yukihiro Matsumoto matz@ruby-lang.org wrote:

Hi,

In message “Re: Ruby: politics & performance [long]” > on 03/01/13, ts decoux@moulon.inra.fr writes:

Not the second word, the second element. For example actually you have

last = list;
while (last->nd_next) {
last = last->nd_next;
}

Try to replace it with

if (list->nd_next) {
last = list->nd_next->nd_end;
}
else {
last = list;
}

i.e. the first element give the size, the second give the end.

You just need to adapt one macro in eval.c to make it work (if I’m right)

This is interesting. I will try this in 1.8.0.

  					matz.

Cool. That’s the good thing about ‘corner cases’ like the application the
original poster was trying to speed up - they can help us speed up Ruby
(and specifically the parser in this case).

Phil

“Or perhaps the truth is less interesting than the facts?”
Amy Weiss (accusing theregister.co.uk of engaging in ‘tabloid journalism’)
Senior VP, Communications
Recording Industry Association of America

28

Hi,

···

In message “Re: Ruby: politics & performance [long]” on 03/01/14, ts decoux@moulon.inra.fr writes:

This is interesting. I will try this in 1.8.0.

Something like this (not fully tested)

Thank you!

						matz.