Re: Difficulties with performance in ATS

2018-08-05 Thread Vanessa McHale 
Yes indeed! This seems to be as fast as the C code. I can't find any
substantial difference, at least. I'll push these changes and take a
look at Hongwei's comments next :)

Thanks!


On 07/20/2018 03:33 AM, Artyom Shalkhakov wrote:
> On Friday, July 20, 2018 at 1:22:47 PM UTC+6, Vanessa McHale wrote:
>
> I'll have to take a look at for/while loops :). With Hongwei's
> suggestion it's nearly as fast as the C code (and it beats two
> common Rust libraries), but I wouldn't mind squeezing the last
> little bit out just for bragging rights (slash ATS advertising).
>
>
>
> Is this any faster?
>
> https://glot.io/snippets/f32psc1xh1
>
> The array is now initialized only once.
>  
>
> On 07/19/2018 11:26 PM, Artyom Shalkhakov wrote:
>> Hi Vanessa,
>>
>> I guess we could improve as follows:
>>
>> 1. just like in C, initialize the array only once (use
>> array_ptr_alloc & array_initize)
>> 2. replace the use of tail-rec functions with while loops :) (in
>> classic C-style ATS)
>> 3. maybe use alloca instead of malloc (since the C example does
>> just that)
>>
>> On Friday, July 20, 2018 at 8:37:13 AM UTC+6, Vanessa McHale wrote:
>>
>> Hi all,
>>
>> I have been working on an implementation of the Levenshtein
>> distance
>> between two strings. I got a working implementation, but it is
>> significantly slower than the C version, viz.
>>
>> #define MIN3(a, b, c) ((a) < (b) ? ((a) < (c) ? (a) : (c)) :
>> ((b) < (c)
>> ? (b) : (c)))
>>
>> // taken from here:
>> 
>> https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C
>> 
>> 
>> int levenshtein(char *s1, char *s2) {
>>     unsigned int s1len, s2len, x, y, lastdiag, olddiag;
>>     s1len = strlen(s1);
>>     s2len = strlen(s2);
>>     unsigned int column[s1len+1];
>>     for (y = 1; y <= s1len; y++)
>>     column[y] = y;
>>     for (x = 1; x <= s2len; x++) {
>>     column[0] = x;
>>     for (y = 1, lastdiag = x-1; y <= s1len; y++) {
>>     olddiag = column[y];
>>     column[y] = MIN3(column[y] + 1, column[y-1] + 1,
>> lastdiag +
>> (s1[y-1] == s2[x-1] ? 0 : 1));
>>     lastdiag = olddiag;
>>     }
>>     }
>>     return(column[s1len]);
>>
>> This is the ATS:
>>
>> staload "prelude/SATS/string.sats"
>>
>> fun min_3(x : int, y : int, z : int) : int =
>>   min(x, (min(y, z)))
>>
>> fun bool2int(x : char, y : char) : int =
>>   if x = y then
>>     0
>>   else
>>     1
>>
>> // Ported over from
>> 
>> https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C
>> 
>> 
>> fn levenshtein {m:nat}{n:nat}(s1 : string(m), s2 : string(n))
>> : int =
>>   let
>>     val s1_l: size_t(m) = length(s1)
>>     val s2_l: size_t(n) = length(s2)
>>     val column: arrszref(int) = arrszref_make_elt(s1_l + 1, 0)
>>    
>>     fun loop1 { i : nat | i <= m } .. (i : int(i)) : void =
>>   case+ i of
>>     | 0 => ()
>>     | i =>> {
>>   val () = column[i] := i
>>   val () = loop1(i - 1)
>>     }
>>    
>>     val () = loop1(sz2i(s1_l))
>>    
>>     fun loop2 { i : nat | i > 0 && i <= n+1 } .. (x :
>> int(i)) :
>> void =
>>   if x <= sz2i(s2_l) then
>>     {
>>   val () = column[0] := x
>>   val () = let
>>     fun inner_loop { j : nat | j > 0 && j <= m+1 }
>> .. (y
>> : int(j), last_diag : int) :
>>   void =
>>   if y <= sz2i(s1_l) then
>>     let
>>   var old_diag = column[y]
>>   val () = column[y] := min_3( column[y] + 1
>>  , column[y - 1] + 1
>>  , last_diag +
>> bool2int(s1[y
>> - 1], s2[x - 1])
>>  )
>>     in
>>   inner_loop(y + 1, old_diag)
>>     end
>>   in
>>     inner_loop(1, x - 1)
>>   end
>>   val () = loop2(x + 1)
>>     }
>>    
>>     val () = loop2(1)
>>   in
>>     column[s1_l]
>>   end
>>
>>

Re: Difficulties with performance in ATS

2018-08-05 Thread Vanessa McHale 
It doesn't seem to affect things in a way that I can measure, though
thankfully with Artyom's suggestions the code is now as fast as C (or at
least, I can't reliably measure any difference in the two) :)

On 07/20/2018 08:39 AM, gmhwxi wrote:
>     fun loop2 { i : nat | i > 0 && i <= n+1 } .. (x : int(i)) :
> void =
>   if x <= sz2i(s2_l) then
>     {
>   val () = column[0] := x
>   val p0 = arrayref2ptr(column)
>   val p1 = ptr_succ(p0)
>   val () = let
>     fun
>     inner_loop
>     { j : nat | j > 0 && j <= m+1 } ..
>     (y : int(j), p0: ptr, p1: ptr, last_diag : int) : void =
>   if y <= sz2i(s1_l) then
>         let
>   fun min_3(x : int, y : int, z : int) : int = min(x,
> (min(y, z)))
>
>   val c0 = $UN.ptr0_get(p0)
>   val c1 = $UN.ptr0_get(p1)
>   val c1_new = min_3(c0+1, c1+1, last_diag +
> bool2int(s1[y - 1]=s2[x - 1]))
>   val () = $UN.ptr0_set(p1, c1_new)
>     in
>   inner_loop(y + 1, p1, ptr_succ(p1), c1)
>         end
>    
>     inner_loop(1, p0, p1, x - 1)
>   end
>   val () = loop2(x + 1)
>     }

-- 
You received this message because you are subscribed to the Google Groups 
"ats-lang-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to ats-lang-users+unsubscr...@googlegroups.com.
To post to this group, send email to ats-lang-users@googlegroups.com.
Visit this group at https://groups.google.com/group/ats-lang-users.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/ats-lang-users/108e32af-a016-2735-1307-9984df9a334f%40iohk.io.


signature.asc
Description: OpenPGP digital signature