OpenEuphoria

1. Optimizing basic operations

• Posted by James_at_Euphoria Jul 21, 2013
• 6436 views

Please inform if any of you have a trick to optimize the simple comparison and assignment operators. I'm especially interested in optimizing this logic: If X is greater than Y then assign the value of X to Y. Is it possible to use something like pointers at a low machine level to speed up the assignment? All of X and all of Y will be integers. Thanks in advance.

3. Re: Optimizing basic operations

• Posted by James_at_Euphoria Jul 21, 2013
• 6454 views

Thanks for such a quick response. I will continue with some testing to compare results. The motivation behind this question is that certain routines involving mathematical functions (factorials, for example) can involve billions or trillions of comparisons as they create a geometric explosion of possibilities. If I use heuristics, IE, trimming the search space / search tree, the probability is that I will find local but not global minimums or maximums. Perhaps after I improve the feature extraction process, assuming that this is possible, the geometric explosion will be smaller (but still very large). In the meantime, every microsecond would help. Again, thanks. P.S. This problem involves pattern recognition.

5. Re: Optimizing basic operations

• Posted by Spock Jul 22, 2013
• 6413 views

James, If I were working on a project like yours and needed ultimate speed I would use assembly code, eg, the following (untested and needing modification) snippet will do this operation without branching:

if eax > ebx then ebx += eax end if

 
  "xor edx, edx" 
  "cmp eax, ebx" 
  "setle dl" 
  "dec edx" 
  "and edx, eax" 
  "add ebx, edx" 

Simply converting this snippet to machine code, poking it somewhere, and calling it with X and Y parameters will not help speed-wise as the overhead of actually calling the machine code routine will completely offset the very real speed gains that you would get from it.

Now, there are some (I'm talking about people on other programming forums..) who don't worry much about code speed, probably because they don't get to code much beyond some lame business app, but the plain truth is that the faster you can go the more you can do.

If it were possible to access X and Y in a linear fashion (in the algorithm) it would probably be not too difficult to construct a small assembly code framework to do all the processing. However, if you needed to do some fancy memory allocation or something tricky (eg, recursion) as part of the algorithm, well, things might get too complex to contemplate using asm.

Exactly what is your algorithm? It might be possible to realize it using asm, or maybe not.

Spock

7. Re: Optimizing basic operations

• Posted by James_at_Euphoria Jul 22, 2013
• 6375 views

Good. I was thinking of the same thing: a hybrid with Euphoria calls to the lower level routines. Thanks for the confirmation. That saves me a lot of testing.

9. Re: Optimizing basic operations

• Posted by jaygade Jul 22, 2013
• 6359 views

One of the things to look at too is ease and speed of development. Do your prototype first in Euphoria. If you don't get your required performance then you can either translate it to C using the translator, or translate it to C or assembly manually.

Euphoria should be very fast with integer math, though not as fast as finely-tuned C or SIMD assembly instructions.

11. Re: Optimizing basic operations

• Posted by James_at_Euphoria Jul 30, 2013
• 6049 views

My first goal was to look at the sorting process. I noticed that shell_sort works best in general, but there are still many situations where it does not. For example, if the list to be sorted is already sorted, bubble_sort comes out on top. If the list is completely sorted except for the last entry (the insertion), then, not surprisingly, insertion_sort is faster. Additionally, there appears to be worst-case scenarios which can find each of the sorts' weak points. If I remember correctly, in the allsorts.ex program, size variables were set to nitems = 500 and length of list = 17 (using the repeat statement). But the results can be deceiving. because just changing these values (and not the type of data) will alter the relative ranking of the performance of each sort, that is, some will do better than others depending on the situation. I now realize that my original question about optimization had a hidden meaning. There is low level optimization such as n += 1 appears faster than n = n + 1 and high level optimization (situation based). The bucket_sort works best in certain restricted situation because it avoids the comparison operator. Is there a performance penalty for using ">", compare() or equal()? Is there a performance penalty if I use a loop to extract elements of a list instead of splicing into it? (Yes, I think so.) While there may be many ways to skin a cat, some are faster than others. Is there a resource guide that addresses some of these issues?

13. Re: Optimizing basic operations

• Posted by jaygade Jul 31, 2013
• 6071 views

I hope that I'm not pointing out the obvious, but this is true for all computer languages, it's a feature of the given algorithms themselves.

Some sorts work better under given conditions, and some sorts work worse. http://en.wikipedia.org/wiki/Sorting_algorithm

If you have some insight into your data, then you can pick the best representation and sorting method based on those insights. Otherwise you have to be more general.

I haven't actually tried this, and it may be due to the distribution of the random data, but while a couple of algorithms may swap places, some still stay on top for random data and some still stay near the bottom?

I'll have to check.

Actually, I think that the Euphoria interpreter is smart enough to handle these two cases the same. The n += 1 is just syntactic sugar.

However, Euphoria does optimize n + 1 vs n + x. http://openeuphoria.org/docs/perform.html#_723_somespecialcaseoptimizations

Yes, the first and best optimization is choosing the correct algorithm. Again, that's true for every language.

Usually it's best to leave the low-level optimizations to the interpreter or compiler, and leave your code clear and easy to read. That way when you go back and look at it six months later, or when someone else reads your code, they can more easily understand it.

That doesn't always hold true, but it's a good general guideline. However, having a low-level understanding of how the computer works can help you with choice of algorithm or choice of algorithm steps.

Using '>' or '=' on sequence types works slightly differently in Euphoria, so they're not really comparable. However, using '=' vs 'equals' on atoms or integers should have the same performance.

With regards to sequence operations, you can be pretty sure that any built-in sequence operations are more optimal than looping over a sequence manually. However, there are many cases where looping manually is still required.

If you are interested in what Euphoria is doing at a low level with a given piece of code, Euphoria does have an IL disassembler so you can examine the low level operations performed at the interpreter level. You can also translate to C and examine that output. Or you could browse the source and get a look at what's going on under the hood.

All three are good ways to compare optimizations.

15. Re: Optimizing basic operations

• Posted by James_at_Euphoria Jul 31, 2013
• 5943 views
• Last edited Aug 02, 2013

I don't know how to post a graphic file, so here is the output I have. Benchmark results for allsorts.ex. Data to sort has been altered to be lists of integers and not just integers. Bucket_sort was modified to handle this more complex scenario. P.S. If you can see this in graphic form, the performance degradation becomes more clear, as well as the relative ranking of each algorithm. Also, the timer mechanism was not always exact as small differences could occur with no warning or explanation.

Number of completed sorts for 100 items

lists to sort: 2
bubble_sort 847038
simple_sort 908010
insertion_sort 841821
merge_sort 290386
quick_sort 302878
hybrid_sort 698569
great_sort 584590
shell_sort 759986
modified_bucket_sort 93597

lists to sort: 4
bubble_sort 246500
simple_sort 294474
insertion_sort 347594
merge_sort 100568
quick_sort 154605
hybrid_sort 313143
great_sort 265166
shell_sort 378903
modified_bucket_sort 82363

lists to sort: 8
bubble_sort 86490
simple_sort 98159
insertion_sort 152453
merge_sort 40193
quick_sort 70306
hybrid_sort 143642
great_sort 126617
shell_sort 179590
modified_bucket_sort 64797

lists to sort: 16
bubble_sort 19945
simple_sort 24247
insertion_sort 41213
merge_sort 13739
quick_sort 20469
hybrid_sort 43532
great_sort 39388
shell_sort 63232
modified_bucket_sort 40378

lists to sort: 32
bubble_sort 5923
simple_sort 6790
insertion_sort 13430
merge_sort 6682
quick_sort 10453
hybrid_sort 21189
great_sort 18304
shell_sort 23251
modified_bucket_sort 22340

lists to sort: 64
bubble_sort 1412
simple_sort 1721
insertion_sort 3917
merge_sort 3017
quick_sort 4067
hybrid_sort 7455
great_sort 6403
shell_sort 10628
modified_bucket_sort 12287

lists to sort: 128
bubble_sort 362
simple_sort 423
insertion_sort 930
merge_sort 1351
quick_sort 2309
hybrid_sort 3371
great_sort 3127
shell_sort 4058
modified_bucket_sort 5303

lists to sort: 256
bubble_sort 81
simple_sort 101
insertion_sort 218
merge_sort 515
quick_sort 728
hybrid_sort 1177
great_sort 1333
shell_sort 1755
modified_bucket_sort 2475

lists to sort: 512
bubble_sort 22
simple_sort 26
insertion_sort 57
merge_sort 260
quick_sort 403
hybrid_sort 519
great_sort 528
shell_sort 627
modified_bucket_sort 1179

lists to sort: 1024
bubble_sort 6
simple_sort 7
insertion_sort 15
merge_sort 124
quick_sort 198
hybrid_sort 263
great_sort 263
shell_sort 277
modified_bucket_sort 482

lists to sort: 2048
bubble_sort 2
simple_sort 2
insertion_sort 4
merge_sort 55
quick_sort 83
hybrid_sort 105
great_sort 112
shell_sort 121
modified_bucket_sort 214

lists to sort: 4096
bubble_sort 1
simple_sort 1
insertion_sort 1
merge_sort 21
quick_sort 34
hybrid_sort 43
great_sort 37
shell_sort 39
modified_bucket_sort 79

lists to sort: 8192
merge_sort 12
quick_sort 17
hybrid_sort 20
great_sort 23
shell_sort 17
modified_bucket_sort 32

lists to sort: 16384
merge_sort 6
quick_sort 7
hybrid_sort 8
great_sort 10
shell_sort 7
modified_bucket_sort 13

lists to sort: 32768
merge_sort
quick_sort 3
hybrid_sort 3
great_sort 4
shell_sort 4
modified_bucket_sort 5

lists to sort: 65536
merge_sort 2
quick_sort 2
hybrid_sort 2
great_sort 2
shell_sort 2
modified_bucket_sort 2

p.s. I'm still learning the format options. I'm trying to make my benchmarks clear. Any way to post a graph for you guys?

17. Re: Optimizing basic operations

• Posted by jaygade Jul 31, 2013
• 5927 views

Which element are you sorting on? If you are sorting on one of the integer groups, how do you determine ordering? That is, whether one group is greater than, less than, or equal to another group?

Have you looked at the functions in std/sort.e? http://openeuphoria.org/docs/std_sort.html#_2964_sorting

Edit: Never mind, I see the answer in my quoted section above.

I'll come up with a code snippet later.

19. Re: Optimizing basic operations

• Posted by James_at_Euphoria Aug 01, 2013
• 5863 views

Good point. I'll focus on index sorts. Each group of integers currently has about 25 elements, possibly more if I can make an efficient sort. Think of trillions of these data structures coming in sequentially. From that blitz of data, I'm interested in the top 100 scores... So, one option is to make the top 100 list and then sort each new eval that comes in. This is probably not efficient. The other is to wait until all eval scores are in, but this is probably not efficient and there isn't enough memory. Looking at the performance data I posted early, there has to be some kind of "sweet spot" between 1 and 1 trillion. Let's call that number "n". So, I'll wait until my "bucket" has n elements, append the bucket to my current top 100 list, create list with only the eval and the index, sort, and then pull out the new top 100 by using the index. The evals and data that don't make the top 100 are rejected. In fact, in this case, I might test to see if the new evals are at least greater than the lowest eval on my top 100 list before putting it into the bucket. That's probably cheaper than sorting it later. (Now you see why I was asking about optimization at all levels).

21. Re: Optimizing basic operations

• Posted by jaygade Aug 01, 2013
• 5855 views

Let me see if I understand your problem so far:

1. Receive a data structure containing an evaluation and two lists of 25 integers. The evaluation is the result of some calculation.
2. Add the data to a list, keeping the list sorted by the value of evaluation as the data are received sequentially.
3. The list can grow to a very large size.

This sounds like a good combination for insertion sort from the standard library, especially if scores will be coming in sequentially. I believe that it will be more efficient to build and maintain a sorted list than it will be to read in all the values and sort them afterward. Especially if you are talking "trillions of values". You may not even be able to keep the entire list in memory at once. Edit: The only constraint is if you somehow receive more values than you can sort in a certain amount of time.

Is the evaluation dependent on either list of 25 integers? Do the integer lists need to be sorted independently?

Note: I'm not an expert on sorting itself, just my reading of the manual and layman's knowledge of sorting and complexity.

Can you give a better pseudocode explanation of what you are trying to do? I started working on a test/example from what you had said before, but your new information brings with it new assumptions.

23. Re: Optimizing basic operations

• Posted by gimlet Aug 01, 2013
• 5857 views

As you are interested in the top 100.

1 Sort to first 100.

2 then:

25. Re: Optimizing basic operations

• Posted by Euman Aug 02, 2013
• 5806 views

Have you seen this bucket_sort method.. if we are now in the sorting mode? (scratches head)
Sunday, Feb. 23th, 1997 Robert Craig proposed a sort without any comparison:

function bucket_sort(sequence s, integer min_value, integer max_value) 
-- Sort s into ascending order. No elements are compared. 
-- The values of s must be integers from min_value to max_value 
    sequence count, sorted 
    integer value 
 
    count = repeat(0, max_value-min_value+1) 
    s = s - (min_value - 1) 
    for i = 1 to length(s) do 
        value = s[i] 
        count[value] = count[value]+1 
    end for 
    sorted = {} 
    for i = 1 to length(count) do 
        sorted = sorted & repeat(i, count[i]) 
    end for 
    return sorted + (min_value - 1) 
end function 
 
? bucket_sort({25,7,2,5,200,14,7,10}, 1, 256) 

27. Re: Optimizing basic operations

• Posted by James_at_Euphoria Aug 02, 2013
• 5829 views

The evaluation is the result of a calculation based on the two groups of 25 integers. The two integer groups (lists) associated with the evaluation are already sorted by this point.

29. Re: Optimizing basic operations

• Posted by Spock Aug 02, 2013
• 5794 views

James,

If you only need to find the top 100 out of trillions then the problem is not really about fast sorting, its about fast maintenance of an already sorted list, eg:

seq list = first100elements() 
list = sort( list ) 
integer lowest = lowestEval( list ) 
for i = 101 to a trillion less 100 do 
  obj this = next_item() -- get next data structure 
  if this > lowest then 
    shufflelist(list, this) 
    lowest = lowestEval( list ) 
  end if 
end for 

I hope you can follow the logic in this pseudo code. The inner test will most likely be NOT taken. But when it is you can casually update the list, via shufflelist(), which you have to write. Most (like 99.999%) of the time will be spent just looping (ignoring the overhead of next_itme()) so this is about as good as you will get with plain Euphoria.

When the loop exits list will contain the top 100.

shufflelist() simply inserts "this" somewhere in list and drops the last element.

I think this should be good enough for your needs.

regards, Spock

31. Re: Optimizing basic operations

• Posted by Spock Aug 02, 2013
• 5731 views

Yes. shufflelist() should be faster than sort() but the efficiency of that part of the program is a minor issue since it will be called so infrequently. The overall processing time will be dominated by the trillions of comparisons needed inside the main loop.

The difference between choosing sort() or shufflelist() might mean the difference between a processing time of 10 hours versus 10 hours and 2 seconds. A much bigger concern is the derivation of the data structures in the first place. Tell us about that, there could be some sizeable gains to be had.

regards, Spock

33. Re: Optimizing basic operations

• Posted by James_at_Euphoria Aug 03, 2013
• 5703 views

Thanks, Lonny, for the reality check. I'm concerned about this as well. I guess if I'm in a hurry I might have to rent a machine that can do up to 240 teraflops. Then I might be able to turn 11+ days into an hour or so. See:

http://www.extremetech.com/computing/96829-rent-the-worlds-30th-fastest-30472-core-supercomputer-for-1279-per-hour

I can also change the threshold (sensitivity) of the data and reduce the number of records. Additionally, I'm also looking at heuristic approaches to prune the search tree. However, these approaches risk skipping over the best solution(s).

35. Re: Optimizing basic operations

• Posted by Euman Aug 03, 2013
• 5637 views

well if its top secret.. then shhhhhh if not, just tell us so we can all stop scratching our head.. just saying

37. Re: Optimizing basic operations

• Posted by DerekParnell (admin) Aug 03, 2013
• 5646 views

Simple, don't use the internet.

39. Re: Optimizing basic operations

• Posted by James_at_Euphoria Aug 04, 2013
• 5575 views

As an example of my original question about "optimizing basic operations", you'll find that this code works up to 10% faster than the original bucket_sort, depending on the the number of items (nitems).

	-- Sort s into ascending order. No elements are compared. 
	-- The values of s must be integers from min_value to max_value. 
	sequence count, sorted 
	integer k, offset, c	 
	count = repeat(0, max_value - min_value + 1) 
	offset = min_value - 1 
 
	-- count the number of occurrences of each integer value: 
	for i = 1 to length(s) do 
--              value = s[i] - offset 
--		count[value] += 1 
 
		count[ s[i] - offset ] += 1 
	end for 
 
-- 	sorted = repeat(0, length(s)) 
        sorted = s 
 
	k = 1 
	-- make the resulting sorted sequence 
	for i = 1 to length(count) do 
		c = count[i] 
		if c then 
			sorted[k .. k + c - 1] = i + offset 
--			     s[k .. k + c - 1] = i + offset 
			k += c 
		end if 
	end for 
 
	return sorted 
end function 

41. Re: Optimizing basic operations

• Posted by gimlet Aug 05, 2013
• 5512 views

Basically you are doing too much work. The only requirements we really need are:

1. That we know the minimum record for the top 100, the others do not concern us.

2. A data structure which will efficiently provide us with that (eg: a heap). See Wikipedia 'Heap (data structure)' only reverse the conditon so that root is the minimum and items are greater than or equal to their parent node.

create heap H 
for i = 1 to 100 
	insert R.i into H 
end  
 
for i = 101 to N do 
	if R.i > H.min then 
                drop H.min '(root) 
		insert R.i into H 
	end if 
end for 
 
sort H (it's already half-sorted). 

This is a good solution as it uses constant space and an (optimal) single read of the data.

43. Re: Optimizing basic operations

• Posted by DerekParnell (admin) Aug 10, 2013
• 5039 views

I stand corrected. Out of curiosity, I wrote a basic heap (priority queue) library and tested your idea with it and it was about three times faster than my first efforts. In fact, I can process a billion records in about 40 seconds.

If anyone is interested, I'll submit the library for public/peer review and thus possible inclusion into the standard library.

45. Re: Optimizing basic operations

• Posted by useless_ Aug 10, 2013
• 5050 views

I was afraid to ask for it.

useless

47. Re: Optimizing basic operations

• Posted by gimlet Aug 16, 2013
• 4589 views

James,

The talk has mostly been about the speed of processing the data. 
 
You need to consider first of all the upload time. Given 10^12 records 
with a evaluuation integer and 50 numbers you have a very large amount 
to load. say 200 Tb. 
 
According to Tom's hardware the fastest off the shelf and affordable 
SSDs have data transfer rates approximating 0.5 Gb per second. That is 
to say you would be looking at an upload time of 400,000 seconds or so. 
 
That is 111 hours or 4.5 days.  
 
The processing of the records (assuming random data) could be expected 
to be 40,000 seconds (based on Derek's numbers). That is to say  
11 hours.  
 
Multiplying the number of machines used is much more effective than  
using a faster processor. Eg 10 machines would get the load time down  
to 11 hours and the processing down to 1.1 hours.  
 
Cutting down the amount of data would also help (but, of course you  
still need to have the identifying data together with the evaluation). 

49. Re: Optimizing basic operations

• Posted by James_at_Euphoria Aug 17, 2013
• 4455 views

Your work is much appreciated.

51. Re: Optimizing basic operations

• Posted by gimlet Aug 21, 2013
• 4279 views

Derek,

Looking at your code I notice that your implementation of
insert_record is faulty. If you insert data on increasing
key values into a max-heap the code appears to generate a
linked list.

You say that the tree is not balanced: but a heap is
required to be a coplete tree - no gaps except the bottom
row which is filled from left to right.

Code attached: (untested)

(* This is for a max-heap *)

const M = 256;                       (* say *) 
 
type  rec = array[1..26] of integer; (* say *) 
 
var   Heap : array[1..M,0..1] of integer; 
      N : integer := 0; 
	  Data : array[1..M] of rec; 
 
(* Two procedures siftUp and siftDown which move a node *) 
(* into its correct position in the heap. *) 
 
procedure siftUp; 
var i,p,t : integer; 
begin 
	i := N; 
	while i > 1 do 
		p := i div 2; 
		if Heap[i,0] > Heap[p,0] then  (* swap *) 
		begin 
			t := Heap[i]; 
			Heap[i] := Heap[p]; 
			Heap[p] := t; 
			i := c 
		end 
		else                 (* stop *) 
			exit while; 
	end 
end; (* siftUp *) 
 
procedure siftDown; 
var i,c,t : integer; 
begin 
    i := 1; 
	c := 2; 
	while c <= N do 
	begin 
		if c < N and Heap[c,0] < Heap[c+1,0] then c := c+1; 
		if Heap[c,0] > Heap[i,0] then 
			t := Heap[c]; 
			Heap[c] := Heap[i]; 
     		Heap[i] := t; 
		    i := c; 
		    c := 2*c 
	    else (* stop *) 
		    exit while; 
	end; 
end; (* siftDown *) 
 
(* Three procedures to add, remove and replace nodes. 
   Addition is always done at the end - it is the only 
   action that can cause an overflow. Take always takes 
   the root and can cause an underflow. Replace is not 
   required - it was written with respect to James's 
   problem find the top 100 elements in a list. *) 
 
procedure add(r : rec); 
begin 
	N := N+1;            (* add a node *) 
	Heap[N,0] := r[1]; 
    Data[Heap[N,1]] := r; 
    siftUp; 
end; (* add *) 
 
function take : rec; 
var r integer; 
begin 
    r := Heap[1,1]; 
	Heap[1] := Heap[N];  (* copies both node value and pointer *) 
    Heap[N,1] := r;      (* N now points to the record to be dropped *) 
	N := N-1; 
	siftDown; 
	take := Data[r] 
end; (* take *) 
 
procedure replace(r : rec); 
begin 
	Heap[1,0] := r[1]; 
	Data[Heap[1,1]] := r; (* overwrites with new record *) 
	siftDown; 
end; (* replace *) 

53. Re: Optimizing basic operations

• Posted by gimlet Aug 21, 2013
• 4160 views

Derek,

The point of using a heap is that it give O log N insert and extract min/max. It
is the basis of heapsort.

There are faults in your method:

1 Your method allows a wildly unbalanced tree. This is not the description of a heap.
Whether your heap would balance out in the long run - maybe - probably not.

2 Inserting from the top does not build a correct priority queue as it will
produce last in first out for any given priority. I don't think we want
to model queue-jumping.

3 Testing with random key data will generate a balanced tree - as such it is not a fair
test.

4 When you do extract min/max you promote one of its children - this may further
unbalance your tree.

The (standard) array approach is clean and simple. Is there some pressing reason
that requires you use pointers? Your code is quite complex.