| Author |
Message
|
| pyrus |
 Posted: Wed Aug 18, 2010 5:09 am Post subject: |
 |
|
Novice
Joined: 20 Jul 2007
Posts: 16
Location: Belgium
|
@mqsiuser
Ok I kind of came to the same conclusion, the recursive character of the function makes for more resource usage, but... what I don't understand is that most of the variables used are actually references and I tried setting some to NULL before which made the tree structure (to which they were pointing) completely disappear, as expected. In other words I don't think references use all that much memory. Maybe the broker is just really wastefull with resources when it comes to a new instance of a function....
How is it that basic execution group memory usage + one messages of slightly under 8MB make the memory usage peak at over 2GB (both physical and virtual memory). I can't see the memory hog in my code OR in the quickSort...
_________________
Connectivity Cowboy |
|
| Back to top |
|
 |
| mqsiuser |
| Posted: Wed Aug 18, 2010 6:42 am Post subject: |
|
|
Yatiri
Joined: 15 Apr 2008
Posts: 637
Location: Germany
|
I had problems when recursing into significant depths. I made several adjustments to quickSort to make the recursion-tree relatively flat (including that quickSort does not easily degenerate) because of the recursion-depth-limit in Message Broker (or probably it is a limit of the underlying platform/OS). I don't know the exact number (must be something between 100 and 1000). Unfortunately the execgroup just hangs and there is no exception or controlled aboard when you get too deep. As you say, probably "to call a function" requires (too) much resources. Or as you say the problem might be limitations on the depth of the function call-stack. Does anybody know of a Unix, C or Broker parameter according to that?
You are processing a lot in a single message. If a message is flat file and (significantly) below the 100 MB-limit of MQ (e.g. 8MB) it can still expand significantly during parsing. On a project I made execgroups crash by just parsing in flat-file-messages into the logical-message-tree. What is the mem-usage when you do nothing but just reading in the message?
Btw... there are programming techniques were you can resolve recursion into non-recursion  . I think it is very likely that we can remove the function-call-recursion (at all) and use the (logical) tree-structure (to mimic recursion). If there are no limits on the depth of the Message-Broker-tree-structure this might be a solution. There are some possibilities... probably we can avoid recursion at all and do something "in place". (I will have a look at it).
Last edited by mqsiuser on Wed Aug 18, 2010 11:00 am; edited 9 times in total |
|
| Back to top |
|
|
| mqjeff |
| Posted: Wed Aug 18, 2010 7:06 am Post subject: |
|
|
Grand Master
Joined: 25 Jun 2008
Posts: 17447
|
It honestly may be faster, more reliable, and cleaner to insert the records into a temporary database table indexed off of the appropriate value and then use PASSTHROUGH to ORDER BY, potentially using a result set of some kind to pull out chunks.
When dealing with this many records, you do need to spend time and effort on reviewing your code for how you handle memory, in particular on when you can get away with DELETEing elements and on taking advantage of the streaming parsers where you can.
There's a devWorks article somewhere on this.
You might also construct an intermediate tree in Environment that contains the relevant sort key and a REFERENCE to the related element in the Input tree. Then use the quicksort algorithm on the INTERMEDIATE tree, and walk the sorted result to produce your output message. |
|
| Back to top |
|
|
| mqjeff |
| Posted: Wed Aug 18, 2010 11:24 am Post subject: |
|
|
Grand Master
Joined: 25 Jun 2008
Posts: 17447
|
And, I keep forgetting about this..
Broker v7 includes Sequence and Resequence nodes that can be used to do this level of sorting across a set of messages. So you may wish to investigate using those instead. |
|
| Back to top |
|
|
| pyrus |
| Posted: Thu Aug 19, 2010 3:34 am Post subject: |
|
|
Novice
Joined: 20 Jul 2007
Posts: 16
Location: Belgium
|
Unfortunately we are using broker 6.1 and I don't beleve we will be upgrading any time soon.
However... I did think of the easiest solution you could imagine, why would we want to sort any messagetree if it's possible to insert all the keyvalues into a table and then use 'SELECT DISTINCT' which gives you a good list to use for SELECT on the InputRoot. In this way it's possible to loop over all keyvalues without deleting the data from the tree and not process the same repeating element twice.
In this way sorting or grouping is no longer necessary, not a solution if you really want a specific order, but I only needed grouping, maybe that wasn't very clear from my posts.
Actually as I think of it one could also do an order by with passthru if it is necessary.
_________________
Connectivity Cowboy |
|
| Back to top |
|
|
| mqsiuser |
| Posted: Thu Aug 26, 2010 1:45 pm Post subject: |
|
|
Yatiri
Joined: 15 Apr 2008
Posts: 637
Location: Germany
|
Hello,
I have rewritten quickSort to use the (logical)message-tree to do recursion (instead of "function-call-recursion").
The code is now moved to the initial Code posting (see earlier post in this thread). I don't see a need for having to call functions recursively (the tree itself should be good enough to base the recursion on) so the old implementation is superseded by this one!
I was able to sort 140.000 siblings within some seconds with this implementation.
Please feel free to test quickSort intensely and provide feedback.
Last edited by mqsiuser on Tue Jul 12, 2011 11:47 pm; edited 1 time in total |
|
| Back to top |
|
|
| mqsiuser |
| Posted: Sun Jan 23, 2011 3:29 am Post subject: |
|
|
Yatiri
Joined: 15 Apr 2008
Posts: 637
Location: Germany
|
Remarks:
(1) quickSort() now uses "DETACH & ATTACH"
(2) QuickSort works now IN PLACE, which means that there are not two variables (one for Input and one for output) any more, but there is just one (in&output-variable, called "refList").
This is because DETACH and ATTACH will only work within the same "structure", e.g. OutputRoot, Environment, ....
I have replaced the code from the initial code posting.
If you sort only to group elements that belong together then aggregate() might be a more proper solution
_________________
Just use REFERENCEs |
|
| Back to top |
|
|
| sunny_30 |
| Posted: Wed Feb 22, 2012 2:17 pm Post subject: |
|
|
Master
Joined: 03 Oct 2005
Posts: 258
|
Thank you mqsiuser for the quicksort !
I just wanted to report a little problem with it.
If the "sibling" is absent, the "WHILE doLoop DO" never comes out..
The sort function works great when # of items to sort are >2
Im not sure if sort items <=2
If 0 as I said it results in infinite loop
Thx |
|
| Back to top |
|
|
| mqsiuser |
| Posted: Wed Feb 22, 2012 11:40 pm Post subject: |
|
|
Yatiri
Joined: 15 Apr 2008
Posts: 637
Location: Germany
|
| sunny_30 wrote: |
The sort function works great when # of items to sort are >2
Im not sure if sort items <=2
If 0 as I said it results in infinite loop |
O.k., might be... I will look at it.
For the time being (and if you have incredibly tight deadlines) you can work around this (potential) problem by:
Before calling quickSort() walk into the first child (sibling of the list). If it is missing you are done. If not walk into the second: If it is missing you are done. If it is there you need to check if there also is a third one. If not compare the second with the first. Depending on the result of the comparison: DETACH the first (sibling) and ATTACH it at the end (behind the second) or do nothing (if they already are in proper order). ELSE (note that at this point you must have at least 3 elements/siblings in your list) use quickSort().
_________________
Just use REFERENCEs |
|
| Back to top |
|
|
| mqsiuser |
| Posted: Tue Feb 28, 2012 3:11 am Post subject: |
|
|
Yatiri
Joined: 15 Apr 2008
Posts: 637
Location: Germany
|
| sunny_30 wrote: |
The sort function works great when # of items to sort are >2
Im not sure if sort items <=2
If 0 as I said it results in infinite loop |
I can confirm that there have been problems when sort items were either zero (0) or one (1). Two (2) worked well for me. I have put in checks for zero (0) and one (1), so this should work now (also).
If you have any more problems, please let me know.
Performance: The sorting of 1,5 Mio elements took 21.5 seconds (that are 70 tsd elements/rows/records per second) on my laptop.
_________________
Just use REFERENCEs |
|
| Back to top |
|
|
| MikeOliverAZ |
| Posted: Wed Sep 24, 2014 3:44 pm Post subject: Question in another thread |
|
|
Apprentice
Joined: 10 Jul 2013
Posts: 47
|
Sorry I posted a question on quickSort to a new thread by mistake.
http://www.mqseries.net/phpBB2/viewtopic.php?p=382086#382086
I can use quickSort very well on complex types where I need to sort on a field in that complex type.
The question is can I and if so how do I sort a simple array?
Schema
| Code: |
<xsd:complexType name="OtherVariablesType">
<xsd:sequence>
<xsd:element maxOccurs="unbounded" minOccurs="1"
name="OVParam1" type="xsd:string" nillable="true" />
<xsd:element maxOccurs="unbounded" minOccurs="1"
name="OVParam2" type="xsd:string" nillable="true" />
<xsd:element maxOccurs="unbounded" minOccurs="1"
name="OVParam3" type="xsd:string" nillable="true" />
<xsd:element maxOccurs="unbounded" minOccurs="1"
name="OVParam4" type="xsd:string" nillable="true" />
<xsd:element maxOccurs="unbounded" minOccurs="1"
name="OVParam5" type="xsd:string" nillable="true" />
</xsd:sequence>
</xsd:complexType>
|
I want to sort the unbounded OVParam5 elements.
What string do I use in the "value" argument to quickSort? |
|
| Back to top |
|
|
| Vitor |
| Posted: Thu Sep 25, 2014 5:52 am Post subject: Re: Question in another thread |
|
|
Grand High Poobah
Joined: 11 Nov 2005
Posts: 26093
Location: Texas, USA
|
| MikeOliverAZ wrote: |
| Sorry I posted a question on quickSort to a new thread by mistake. |
i.e. this one, where you got some advice and got a bit personal.
Frankly, that new thread (rather than posting on this 2 year old one) is the way to go. If you want to reference this 2 year old link, then do so.
Also remember that we are all volunteers, that tone does not translate into text and if you don't think you're getting the help you want here you can raise a PMR.
_________________
Honesty is the best policy.
Insanity is the best defence. |
|
| Back to top |
|
|
| MikeOliverAZ |
| Posted: Thu Sep 25, 2014 3:59 pm Post subject: Re: Question in another thread |
|
|
Apprentice
Joined: 10 Jul 2013
Posts: 47
|
| Vitor wrote: |
| MikeOliverAZ wrote: |
| Sorry I posted a question on quickSort to a new thread by mistake. |
i.e. this one, where you got some advice and got a bit personal.
Frankly, that new thread (rather than posting on this 2 year old one) is the way to go. If you want to reference this 2 year old link, then do so.
Also remember that we are all volunteers, that tone does not translate into text and if you don't think you're getting the help you want here you can raise a PMR. |
Vitor,
Thanks and noted. It is hard sometimes, when someone doesn't answer the question, and pontificates and then denigrates me as if I should know already or must be ignorant if I need to ask such a silly question. It was like I asked what time it was and got an explanation of why timezones exist...oh well, I found another way so the point is moot.
I have ordered a thicker skin but it hasn't arrived yet.
Ollie
_________________
SOACA, Lead Architect Smart Comunications |
|
| Back to top |
|
|
| mqsiuser |
| Posted: Fri Sep 26, 2014 1:11 am Post subject: Re: Question in another thread |
|
|
Yatiri
Joined: 15 Apr 2008
Posts: 637
Location: Germany
|
Vitor, mqjeff and others are right:
New threads should be opened for new questions, but honestly you didn't trigger my attention by doing so.
So posting here -with the regard to trigger the attention of the original author of quicksort (me)- is reasonable (it worked).
Let's move back to http://www.mqseries.net/phpBB2/viewtopic.php?p=382086 ?!
Could you post a simple input (unsorted) (sample xml) and output (sorted) there ?
_________________
Just use REFERENCEs |
|
| Back to top |
|
|
|
|
