Re: call_func is expensive // Phix much slower

new topic     » goto parent     » topic index » view thread      » older message » newer message
_tom said...
Spock said...

I have an idea for enhancing the performance of Msort. If it works well we might be a bit more relaxed about using the lower performance (but increased flexibility) from custom_sort(). Gimme a few days..

Spock

As is, Msort is fast and practical. The simplest way to get performance is to compile, which is the easy way to get (roughly) twice the speed.

But, Euphoria has a legacy of speed; it will be fun to see how things can get faster.

_tom

Well, I had some initial success. I get up to 20% improvement over msort. With some tweaking of constants maybe could extend that to 30%. Here is the algorithm in code. It won't run as is but gives the idea:

 
include bfind.e 
 
function m2sort(seq s) 
 
	-- early out? 
	if ~s < 200 then return insertion_sort(s) end if 
	 
	-- make index 
	seq index = {} 
	for i = 1 to ~s by 20 do 
		index &= { s.i } 
	end for 
	index = m2sort(index) 
 
	-- make the buffer 
	seq store = repeat( {}, ~index ) 
 
	-- store all items in buffer 
	for i = 1 to ~s do 
		obj x = s.i 
		int n = bfind(x, index) 
		store.n &= { x } 
	end for 
 
	-- final sort on all items 
	s = {} 
	for i = 1 to ~store do 
		s &= m2sort( store.i ) 
	end for 
	 
	-- exit 
	return s 
 
	end function 
 

Basically it samples the data and uses that to coarsely place the data into buckets. And then does a final sort of each bucket. BTW, the tilde symbol represents length(). And I have dot notation. For me it's an interesting little side-project. When some more substantial results come through I'll update msort.zip on the contributions page.

Spock

new topic     » goto parent     » topic index » view thread      » older message » newer message

Search



Quick Links

User menu

Not signed in.

Misc Menu