topic Re: Nested loops in Application Development and Automation Discussions

Nested loops

Former Member — Wed, 01 Aug 2007 14:54:09 GMT

Hi,

Do nested loops ( till 2 levels ) also cause for performance issues ?

Please give me detailed info.

Thanks,

Binay.

Re: Nested loops

Former Member — Wed, 01 Aug 2007 14:56:40 GMT

Hi,

Yes, nested loops will give you the performance problem ..

http://www.erpgenie.com/abap/performance.htm#Nested%20selects

Regards

Sudheer

Re: Nested loops

Former Member — Wed, 01 Aug 2007 14:58:02 GMT

Absolutley - please check:

<a href="/people/rob.burbank/blog/2006/02/07/performance-of-nested-loops">Performance of Nested Loops</a>

Rob

Re: Nested loops

seshatalpasai_madala — Wed, 01 Aug 2007 14:59:10 GMT

Hi,

Depends on what you do in the INNER LOOP.

If you are calling a Function module or executing a DB statement then this will obviously have a bad effect on the performance.

Calling an FM is bad since it creats a HUGE stack of CALLING the Function modules.

And DB statements are most precious in terms of performance you should make sure that they are out side the LOOP statement using better select statements and as few statements as possible.

IF you just processing the internal tables your are looping then this should not have much effect on the performance.

Regards,

Sesh

Re: Nested loops

Former Member — Wed, 01 Aug 2007 15:01:58 GMT

it depends on the data available in the internal tables. if data is less using loop and binary search works well.

if data is hughe in all internal tables nested loops might cause a problem but can be avoided using binary search and indexes...

Re: Nested loops

Former Member — Wed, 01 Aug 2007 15:05:06 GMT

Sesh - the problem is more to do with the size of the internal tables rather than what is going on inside them. If you have two internal tables each with say 10,000 records and loop through them with a nested loop. It will take a lot of time even of there is absolutley no processing in the inner loop.

Nested loops can often be a worse problem than a poorly designed SELECT.

Rob

Re: Nested loops

Former Member — Wed, 01 Aug 2007 17:55:06 GMT

Hi Binay,

The parallel cursor is the one of the best and most efficient method in case of nested loops .

It works on the assumption that

loop at TAB1.

loop atTAB2.

end loop.

endloop.

TAB2 contains only entries also contained in TAB1.

Hope it help you.

Let me know If you want to know how to use the parallel cursor algorithm.

Praveen

Re: Nested loops

Former Member — Thu, 02 Aug 2007 05:41:15 GMT

please not user nested loop.

replace as for all entries.

Re: Nested loops

seshatalpasai_madala — Thu, 02 Aug 2007 15:04:33 GMT

Rob_> I just wanted to higlight that calling a SELECT in a LOOP is bad interms of performance. Since we only have on Database server per system and its a costly resource.

Application servers these days can handle more data and have more memory so I didnt empohsize on Size of the internal tables.

Any way I do agree SIZE does have its say on the perofrmance but what you do inside effects even more.

Regards,

Sesh

Re: Nested loops

Former Member — Thu, 02 Aug 2007 15:38:52 GMT

OK Sesh. Here's an example of what I meant:


REPORT ztest MESSAGE-ID 00.

TABLES: bkpf.

PARAMETERS: p_bukrs LIKE bkpf-bukrs,
            p_gjahr LIKE bkpf-gjahr.

DATA: BEGIN OF itab1 OCCURS 0,
        f1,
      END   OF itab1.

DATA: BEGIN OF itab2 OCCURS 0,
        f1,
      END   OF itab2.

DATA: start   TYPE i,
      end     TYPE i,
      dif     TYPE i,
      wa_bkpf TYPE bkpf.

* Get a single document
SELECT * FROM bkpf
  INTO wa_bkpf
  WHERE bukrs = p_bukrs
    AND gjahr = p_gjahr.
  EXIT.
ENDSELECT.

* Fill the internal tables
DO 10000 TIMES.
  APPEND INITIAL LINE TO: itab1, itab2.
ENDDO.

* SELECT within a LOOP
GET RUN TIME FIELD start.
LOOP AT itab1.
  SELECT SINGLE * FROM bkpf
    WHERE bukrs = wa_bkpf-bukrs
      AND belnr = wa_bkpf-belnr
      AND gjahr = wa_bkpf-gjahr.
ENDLOOP.
GET RUN TIME FIELD end.
dif = end - start.
WRITE: /001 'Time for SELECT in a loop:', dif, 'microseconds'.

* Nested LOOP
GET RUN TIME FIELD start.
LOOP AT itab1.
  LOOP AT itab2.
  ENDLOOP.
ENDLOOP.
GET RUN TIME FIELD end.
dif = end - start.
WRITE: /001 'Time for nested loops    :', dif, 'microseconds'.

When I ran this, the nested loops took about thirty times longer than the select within the loop. When I reduced the number of iterations from 10,000 to 1,000, it took about twice as long.

So I believe the size of the tables is the determining factor, not what's going on inside them.

Rob

Re: Nested loops

KjetilKilhavn — Thu, 02 Aug 2007 23:00:52 GMT

OK, I haven't really investigated these issues myself, but I think your example is a bit poorly constructed. I am not saying that nested loops are a good thing, but if comparisons are going to be made they should be realistic and "fair".

1) Your nested loops performs 10.000**2 = 100 million "operations", while the selection only performs 10 thousand operations. How can you then compare the run time of the two? To have comparable operations you should read one (arbitrary?) line from ITAB2 in each iteration.

2) You select the same BKPF dokument every time. That is not realistic, and it most likely means it will be in the buffer after the first select - so in reality you have one selection and N buffer accesses.

The reason I am commenting on this is that I don't want people to be left with the impression that it is better to select the documents to operate on inside a loop than to select all documents into two internal tables and process them in nested loops. Why do I not want that? Because I can't believe it is true. The overhead of multiple accesses to the database should ensure that the double loop is faster, and this difference would increase with the network lag (can be a factor in remote locations for central installations).

Message was edited by Kjetil Kilhavn:

Note: I am not taking memory constraints into consideration, as it was only nested loops that was the topic of the question - not overall performance. For large numbers of internal table entries it may actually be better for overall system performance to select inside each iteration to reduce memory usage.

Message was edited (again!) by Kjetil Kilhavn:

As has already been mentioned; the question is not as simple as "is nested loops a bad thing". It depends on what you do inside the loops, and it depends even more on what alternatives you have available. Sometimes nested loops are the best option, other times the worst.

Hey, no-one said programming was easy, and the difficulty is how we justify our insane hour-rates anyway!

Re: Nested loops

Former Member — Fri, 03 Aug 2007 07:54:58 GMT

I have to say that I don't like most of the answers here, because many things are confused.

Generally nested loops are 2 connected loops over internal tables, I would not talk about selects in the beginning.

loop at itab1

loop at itab2 or read itab2

... some other cheap operations

endloop

=> only if number of entries in itab1 = N1 and N2 (itab2) are large, lets say

N1 * N2 < 10.000, performance becomes important.

Assumption: You never need to loop over itab2 completely for each line of itab1. In business transactions there is always a condition on itab2, as only one or

few corresponding entries of itab2 are needed for each line of itab1.

(Complete nested loops are only necessary in optimization problems)

=> Complete nested loops would need a runtime proportional to N1 * N2

and you have no chance to change it

=> Our problems can be processed in runtimes proportional to N1 * log (N2) !

if you program carefully!

so for

loop at itab1 into wa1

loop at itab2 ... key = wa1-key.

endloop.

+ Dont use loop at itab2 where because this is porportional to N2

+ Use a sorted table for itab2

+ Or

Read itab2 ... binary search.

tabix = sy-tabix

loop at itab2 from tabix.

if ( key ne wa1-key )

exit.

endif.

....

endloop.

Maybe the inner operation needs exactly one line, then use fast reads

+ read on a sorted table

+ read from a standard table with binary search

+ read from hashed table

but not use the simple read from a standard table.

=> Nested loops can produce problems, most of the problems in ABAP coding are related to that, but nearly all of this problems can be avoided, if you program carefully.

Siegfried

Message was edited by:

Siegfried Boes

Re: Nested loops

Former Member — Fri, 03 Aug 2007 13:17:51 GMT

Kjetil:

1) You prove the point I am trying to make. The size of the internal tables is the determining factor, not what goes on inside them.

2) This isn't meant to be a realistic example, just one that is simple and demonstrates what I'm trying to say. But I do tske your point. Buffering will probably be aqn issue here.

I guess my point is - no matter how poorly a SELECT statement is constructed, a nested loop can be constructed that is even worse.

I don't think fairness counts in programming

Rob

Re: Nested loops

KjetilKilhavn — Fri, 03 Aug 2007 21:52:54 GMT

Size matters, we can agree on that. But that is not only relevant for internal tables. A poorly formulated selection on BSEG is much worse than a poorly formulated selection on T001.

However, the example to illustrate your point doesn't really relate to the question. The question is: does 2 levels of nested loops cause a performance problem? I'll still claim the answer is: it depends.

Fairness doesn't count in programming I suppose (point taken , but if you want to compare two things and declare a winner, the comparison should be fair as in comparing similar things. In my opinion you didn't. Well, of course I can compare Claudia Schiffer and George Bush and say I prefer a German over a religious fanatic any day, but what significance does that have to who is the best archer?

Anyway, there are basic rules for performance tuning, but performance tuning can not be done automatically by setting up rules. Hopefully we can agree on that, and that is what I meant by saying that sometimes nested loops are the best solution, and other times the worst. You have to look at the specific case, both the code and the environment.

As was pointed out by Siegfried in his post, you usually do not execute N1 * N2 operations in a nested loop (although that can of course happen), usually you execute only N1 * n2 where n2 is some number smaller than N2. Sometimes you only execute N1 operations (identify only one line from N2), but I'd say those are a good candidate for getting rid of the nested loop - although that's not always possible.

Well, I think this thread turned into a pretty good discussion on the topic at least. That can't be a Bad Thing(tm).

Re: Nested loops

KjetilKilhavn — Fri, 03 Aug 2007 22:10:00 GMT

Siegfried (and anyone else), my curiosity got me over this one.

> + Or

> Read itab2 ... binary search.

> tabix = sy-tabix

> loop at itab2 from tabix.

> if ( key ne wa1-key )

> exit.

> endif.

> ....

> endloop.

Whenever I have a date-dependent buffer (internal table) and need to find the data valid at a certain date I simply use a

LOOP AT buffer 
     WHERE some criteria          AND
           bedga <= relevant_date AND
           endda >= relevant_date.
ENDLOOP.

The internal tables are always sorted - not necessarily TYPE SORTED TABLE, but entries are inserted in sorted order or the internal table is sorted after filling it. My loop will identify the (single) line that is relevant. Are you saying that I would have a faster lookup by using a READ ... BINARY SEARCH followed by a LOOP AT buffer FROM sy-tabix? Usually I do define sorted tables with unique keys. I have assumed that SAP would then quickly find the relevant entry by using a binary search to find the first entry from which the looping should start.

Not that this is where I have had performance problems, but I would be interested in knowing if anyone has studied this to find out if one approach is faster than the other when you need to loop at a subset of entries in a sorted table.

[....]

And this one - that statement got me wondering if it really can be true!

> Nested loops in 3 levels are never necessary!

Can't recall with certainty, but I believe I have used (at least) 3 levels of nested loops in a JVA-report designed for reporting to authorities in Brazil. First loop at the purchase order level, then the invoice level, and finally the payments level - all this in order to find out how much money had been spend on national vs. foreign purchases - reported by payment date but depending on purchase order data for separation between national and foreign. Perhaps I need to call my previous employer and tell them I made a mistake

I know I could have restructured the code to use an internal table with duplicate data, but I don't think there is much performance to gain.

the number of selections would be unchanged
the number of buffer lines iterated over would be the same

Re: Nested loops

Former Member — Mon, 06 Aug 2007 07:03:51 GMT

Hi,

I dropped the comment on 3 levels, because it is possible to write performant 3 level nested loops.

loop at ita1.

loop at sort2 with key k1 = wa1-k1.

loop at sort3 with key k1 = wa1-k1 k2 = wa2-k2.

endloop

endloop.

More important is the other point, a loop at where on a standard table, scans linearly over the whole table, which is slow. Using the binary search to get the index, the loop from index and the exit to leave the loop is much faster. As long as you don't use it, inside of another loop it will just a bug. But if used inside a loop,

it will become your major performance problem. I have detailed measurements.

Siegfried

Re: Nested loops

Neslinn — Tue, 07 Aug 2007 09:36:37 GMT

Hi,

Dont use nested loops.

Use read statements with in the loop.

Neslin,

Re: Nested loops

Former Member — Tue, 07 Aug 2007 10:11:43 GMT

> Dont use nested loops.

> Use read statements with in the loop.

this seems to be a quite common misunderstanding.

You can not use a read when you need a loop! And there is no problem with a nested loop if done correctly.

Siegfried

Re: Nested loops

Former Member — Tue, 07 Aug 2007 14:07:40 GMT

Siegfried and Kjetil - at the risk of beating a dead horse:

First of all, I have been assuming that we are dealing with standard tables only - not sorted. I prefer to use standard tables because they give me more flexibility. I can sort and resort them as needed.

Secondly, for standard tables, except in the most trivial cases, a binary search will be faster. For small tables, it may be not worth the programming effort.

Thirdly, SELECTs in loops should be avoided, but I've never seen an example of a program with poor performance where this was the cause. Poorly constructed SELECTs and nested LOOPs (on standard tables) are generally the cause.

Please see:

<a href="/people/rob.burbank/blog/2006/11/16/performance--what-will-kill-you-and-what-will-leave-you-with-only-a-flesh-wound">Performance - what will kill you and what will leave you with only a flesh wound</a>

Fourthly, you don't need a loop to read all entries of a table. In

<a href="/people/rob.burbank/blog/2006/02/07/performance-of-nested-loops">Performance of Nested Loops</a>

I show one way of accessing all records using a binary search and indexed read on an internal table.

Rob

Re: Nested loops

Former Member — Tue, 07 Aug 2007 14:28:42 GMT

hmm,

I would recommend to use sorted and hashed tables, whenever possible. I know that there is slight advantage of the binary search, but that will never cause a problem.

Problems will be caused to extensive usage of sorts on internal tables, I have seen them inside of loops! The table used in the outer loop must often not be sorted!

Your example with read binary search while read from index is just a more complicated expression of the common solution

read .... with key = x binary search

tabix = sy-index

loop at ... from tabix.

if ( key ne x ).

exit.

endif

endif.

i.e. there is no reason why nested loops should not be used. The workaround above is o.k., with a sorted table it works automatically.

These are completely acceptable solutions. Only in highly critical problems solutions using parallel indexes are necessary.

If I find the time, then I will publish details as a weblog soon.

Siegfried