Ubuntu : Intel® Q6600® one core
Computer Language Benchmarks Game      [[ Play ]]

- all benchmarks - n-body fannkuch-redux meteor-contest fasta fasta-redux spectral-norm reverse-complement mandelbrot k-nucleotide regex-dna pidigits chameneos-redux thread-ring binary-trees-redux binary-trees - all languages - Ada 2005 GNAT ATS C CINT C gcc Clojure C# Mono C++ g++ Dart Erlang HiPE F# Mono Fortran Intel Go Haskell GHC Java 7 JavaScript V8 Lisp SBCL Lua OCaml Pascal Free Pascal Perl PHP Python 3 Racket Ruby 2.0 Ruby JRuby Scala Smalltalk VisualWorks x86 one core x64 quad-core x86 quad-core x64 one core

 performance measurements

Each table row shows performance measurements for this ATS program with a particular command-line input value N.

N	CPU secs	Elapsed secs	Memory KB	Code B	≈ CPU Load
12	0.04	0.05	?	2143	0% 0% 0% 100%
16	0.85	0.85	9,816	2143	1% 0% 0% 100%
20	17.73	17.75	197,256	2143	0% 0% 0% 100%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read binary-trees benchmark to see what this program should do.

 notes

ATS/Anairiats version 0.2.8

 binary-trees ATS #3 program source code

(*
** The Computer Language Benchmarks Game
** http://benchmarksgame.alioth.debian.org/
**
** contributed by Hongwei Xi
**
** compilation command:
**   atscc -D_GNU_SOURCE -D_ATS_MULTITHREAD -O3 binary-trees3.dats -o binary-trees3 -D_ATS_GCATS -lpthread
*)

(* ****** ****** *)

staload "libats/SATS/parworkshop.sats"
staload _ = "libats/DATS/parworkshop.dats"

(* ****** ****** *)

staload _(*anon*) = "prelude/DATS/reference.dats"

(* ****** ****** *)

dataviewtype tree (int) =
  Nil(0) | {n1,n2:two} Node(1) of (tree n1, int, tree n2)

viewtypedef Tree = [n:two] tree n

fun tree_make (d: int, i: int): Tree =
  if d > 0 then
    let val d1 = d-1 and i2 = i << 1 in      
      Node (tree_make (d1, i2 - 1), i, tree_make (d1, i2))
    end
  else Node (Nil (), i, Nil ())
// end of [tree_make]

fun check_and_free (t: Tree):<!ntm> int =  case+ t of
  | ~Node (tl, i, tr) => i + check_and_free tl - check_and_free tr
  | ~Nil () => 0
// end of [check_and_free]

fun check (t: !Tree):<!ntm> int =  case+ t of
  | Node (!tl, i, !tr) =>
    let val ans = i + check (!tl) - check (!tr) in (fold@ t; ans) end
  | Nil () => (fold@ t; 0)
// end of [check]

fun check_ref (r: ref Tree): int = let
  val (vbox pf | p) = ref_get_view_ptr r in check !p     
end // end of [check_ref]

//

#define MIN_DEPTH 4

//

fn stretch (max_depth: Nat): void = let
   val stretch_depth = max_depth + 1
   val t = tree_make (stretch_depth, 0)
   val c = check_and_free (t)
in
   printf ("stretch tree of depth %i\t check: %i\n", @(stretch_depth, c));
end // end of [stretch]

fn long_lived_tree_make
  (max_depth: Nat): ref Tree = let
  val t = tree_make (max_depth, 0); val t_r = ref<Tree> (t)
in
  t_r
end // end of [long_lived_tree_make]

(* ****** ****** *)

fun doWork
  {l_n,l_d,l_c:addr} {d,md:nat | d <= md} (
    pf_n: !int @ l_n
  , pf_d: !int @ l_d
  , pf_c: !int @ l_c
  | p_n: ptr l_n, p_d: ptr l_d, p_c: ptr l_c
  , d: int d, max_depth: int md
  ) : void = let
  val n = 1 << (max_depth - d + MIN_DEPTH)
  fun loop (i: Nat, c: int):<cloref1> int =
    if i < n then let
      val t = tree_make(d,  i); val c1 = check_and_free t
      val t = tree_make(d, ~i); val c2 = check_and_free t
    in
      loop (i+1, c + c1 + c2)
    end else begin
      c // return value
    end // end of [if]
  val () = !p_n := n
  val () = !p_d := d;
  val () = !p_c := loop (0, 0)
in
  // nothing
end // end of [doWork]

(* ****** ****** *)

dataviewtype CONT =
  | CONTnil of ()
  | CONTcons of (int(*n*), int(*d*), int(*c*), CONT)
// end of [CONT]

fun finishup (cont: CONT): void = case+ cont of
  | ~CONTcons (n, d, c, cont) => let
      val () = printf (
        "%i\t trees of depth %i\t check: %i\n", @(2 * n, d, c)
      ) // end of printf
    in
      finishup (cont)
    end (* end of [locklst_cons] *)
  | ~CONTnil () => ()
// end of [finishup]

(* ****** ****** *)

viewtypedef work = () -<lincloptr1> void
viewtypedef WSptr (l:addr) = WORKSHOPptr (work, l)

(* ****** ****** *)

fun fwork {l:addr}
  (ws: !WSptr l, wk: &work >> work?): int = let
  val wk = wk
  val pfun = __cast (wk) where {
    extern castfn __cast
      (wk: !work >> opt (work, i >= 1)): #[i:nat] uintptr i
  } // end of [val]
in
  if pfun >= (uintptr1_of_uint1)1U then let
    prval () = opt_unsome {work} (wk)
    val () = wk ()
    val () = cloptr_free (wk)
  in
    1 // the worker is to continue
  end else let
    val u = uint1_of_uintptr1 (pfun)
    val i = int_of_uint (u)
    prval () = opt_unnone {work} (wk)
    prval () = cleanup_top {work} (wk)
  in
    ~i // the worker is to pause or quit
  end // end of [if]
end // end of [fwork]

(* ****** ****** *)

fun loop_depths {lws:agz}
  (ws: !WSptr lws, d: Nat, max_depth: Nat, res: &CONT? >> CONT): void = let
  extern prfun __ref {v:view} (pf: !v): v
  extern prfun __unref {v:view} (pf: v): void
in
  if d <= max_depth then let
    val () = res := CONTcons (0, 0, 0, ?)
    val+ CONTcons (!p_n, !p_d, !p_c, !p_res1) = res
    stavar l_n:addr and l_d:addr and l_c:addr
    prval pf_n = __ref {int@l_n} (view@ !p_n)
    prval pf_d = __ref {int@l_d} (view@ !p_d)
    prval pf_c = __ref {int@l_c} (view@ !p_c)
    val () = workshop_insert_work (ws, f) where {
      val f = lam (): void =<lincloptr1> let
        val () = doWork (pf_n, pf_d, pf_c | p_n, p_d, p_c, d, max_depth)
        prval () = __unref (pf_n)
        prval () = __unref (pf_d)
        prval () = __unref (pf_c)
      in
        // nothing
      end
    } // end of [workshop_add_work]
    val () = loop_depths (ws, d + 2, max_depth, !p_res1)
  in
    fold@ (res)
  end else begin
    res := CONTnil ()
  end // end of [if]
end (* end of [loop_depths] *)

(* ****** ****** *)

staload "libc/SATS/sched.sats"
staload TYPES = "libc/sys/SATS/types.sats"
macdef pid_t = $TYPES.pid_of_int

extern fun ncore_get (): int
implement ncore_get () = let
  var cs: cpu_set0_t // uninitialized
  prval () = cpusetinit (cs) // not a real initialization
  stavar nset: int
  val nset = cpusetsize_get (cs)
  val () = assert_errmsg (nset >= 2, #LOCATION)
  val err = sched_getaffinity ((pid_t)0, nset, cs)
  var count: Nat = 0
  var i: natLte 16 // uninitialized
  val () = for* (cs: cpu_set_t nset) =>
    (i := 0; i < 16; i := i + 1)
    if (CPU_ISSET (i, cs) > 0) then count := count + 1
  // end of [val]
in
  count
end // end of [ncore_get]

(* ****** ****** *)

#define QSZ 1024

implement main (argc, argv) = let
//
  val () = gc_chunk_count_limit_set (1 << 15)
  val () = gc_chunk_count_limit_max_set (~1) // no max
//
  val () = assert_errmsg
    (argc >= 2, "Exit: wrong command format!\n")
  val n = int1_of argv.[1]
  val () = assert_errmsg
    (n >= 0, "The input integer needs to be a natural number.\n")
//
  val NWORKER = ncore_get ()
  val nworker =
    (if (argc >= 3) then int_of argv.[2] else NWORKER): int
  val nworker = int1_of_int(nworker)
  val () = assert_errmsg (nworker >= 1, #LOCATION)
  val ws = workshop_make<work> (QSZ, fwork)
  val _err = workshop_add_nworker (ws, nworker)
  val () = assert_errmsg (_err = 0, #LOCATION)
//
  val max_depth = max (MIN_DEPTH + 2, n)
  var res: CONT // uninitialized
  val () = loop_depths (ws, MIN_DEPTH, max_depth, res)
  val () = stretch (max_depth)
  val long_lived_tree = long_lived_tree_make (max_depth)
//
  val () = workshop_wait_blocked_all (ws)
  val () = finishup (res)
//
  var i: Nat = 0
  val () = while (i < nworker) let
    val _quit = $extval (work, "(void*)0")
    val () = workshop_insert_work (ws, _quit) in i := i + 1
  end // end of [val]
  val () = workshop_wait_quit_all (ws)
  val () = workshop_free_vt_exn (ws)
in
  printf ("long lived tree of depth %i\t check: %i\n", @(max_depth, check_ref long_lived_tree))
end // end of [main]

(* ****** ****** *)

(* end of [binary-tree3.dats] *)

 make, command-line, and program output logs

Wed, 23 Jan 2013 06:04:20 GMT

MAKE:
/usr/local/src/ats-lang-anairiats-0.2.9/bin/atscc -D_GNU_SOURCE -D_ATS_MULTITHREAD -D_ATS_GCATS -lpthread -pipe -Wall -O3 -fomit-frame-pointer -march=native  binarytrees.dats -o binarytrees.ats-3.ats_run 
/usr/local/src/ats-lang-anairiats-0.2.9/bin/atsopt --output binarytrees_dats.c --dynamic binarytrees.dats
/usr/local/src/ats-lang-anairiats-0.2.9/ccomp/runtime/ats_prelude.c: In function ‘ats_pthread_create_detached’:
/usr/local/src/ats-lang-anairiats-0.2.9/ccomp/runtime/ats_prelude.c:181:3: warning: implicit declaration of function ‘gc_pthread_create’ [-Wimplicit-function-declaration]
In file included from binarytrees_dats.c:19:0:
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/basics.cats: In function ‘atspre_fprint_newline’:
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/basics.cats:271:11: warning: variable ‘n2’ set but not used [-Wunused-but-set-variable]
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/basics.cats:271:7: warning: variable ‘n1’ set but not used [-Wunused-but-set-variable]
binarytrees_dats.c: In function ‘tree_make_0’:
binarytrees_dats.c:294:1: warning: label ‘__ats_lab_tree_make_0’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘check_and_free_1’:
binarytrees_dats.c:351:1: warning: label ‘__ats_lab_1_1’ defined but not used [-Wunused-label]
binarytrees_dats.c:337:1: warning: label ‘__ats_lab_0_1’ defined but not used [-Wunused-label]
binarytrees_dats.c:335:1: warning: label ‘__ats_lab_0_0’ defined but not used [-Wunused-label]
binarytrees_dats.c:332:1: warning: label ‘__ats_lab_check_and_free_1’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘check_2’:
binarytrees_dats.c:395:1: warning: label ‘__ats_lab_3_1’ defined but not used [-Wunused-label]
binarytrees_dats.c:380:1: warning: label ‘__ats_lab_2_1’ defined but not used [-Wunused-label]
binarytrees_dats.c:378:1: warning: label ‘__ats_lab_2_0’ defined but not used [-Wunused-label]
binarytrees_dats.c:375:1: warning: label ‘__ats_lab_check_2’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘check_ref_3’:
binarytrees_dats.c:413:1: warning: label ‘__ats_lab_check_ref_3’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘stretch_4’:
binarytrees_dats.c:432:1: warning: label ‘__ats_lab_stretch_4’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘ref_01033_ats_ptr_type’:
binarytrees_dats.c:450:1: warning: label ‘__ats_lab_ref_01033_ats_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘long_lived_tree_make_5’:
binarytrees_dats.c:467:1: warning: label ‘__ats_lab_long_lived_tree_make_5’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘doWork_7’:
binarytrees_dats.c:551:1: warning: label ‘__ats_lab_doWork_7’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘finishup_9’:
binarytrees_dats.c:597:1: warning: label ‘__ats_lab_5_1’ defined but not used [-Wunused-label]
binarytrees_dats.c:582:1: warning: label ‘__ats_lab_4_1’ defined but not used [-Wunused-label]
binarytrees_dats.c:580:1: warning: label ‘__ats_lab_4_0’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘fwork_10’:
binarytrees_dats.c:618:1: warning: label ‘__ats_lab_fwork_10’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘__ats_fun_12’:
binarytrees_dats.c:642:1: warning: label ‘__ats_lab___ats_fun_12’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘DEQUEptrnxt_01765_ats_clo_ptr_type’:
binarytrees_dats.c:693:1: warning: label ‘__ats_lab_DEQUEptrnxt_01765_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘deque_insert_end_01746_ats_clo_ptr_type’:
binarytrees_dats.c:722:1: warning: label ‘__ats_lab_deque_insert_end_01746_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘queue_insert_01723_ats_clo_ptr_type’:
binarytrees_dats.c:743:1: warning: label ‘__ats_lab_queue_insert_01723_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘workshop_insert_work_01702_ats_clo_ptr_type’:
binarytrees_dats.c:806:1: warning: label ‘__ats_lab_workshop_insert_work_01702_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘_2home_2dunham_2benchmarksgame_onecore_2binarytrees_2tmp_2binarytrees_2edats__ncore_get’:
binarytrees_dats.c:907:1: warning: label ‘__ats_lab_7’ defined but not used [-Wunused-label]
binarytrees_dats.c:904:1: warning: label ‘__ats_lab_8’ defined but not used [-Wunused-label]
binarytrees_dats.c:881:1: warning: label ‘__ats_lab__2home_2dunham_2benchmarksgame_onecore_2binarytrees_2tmp_2binarytrees_2edats__ncore_get’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘workshop_make_01695_ats_clo_ptr_type’:
binarytrees_dats.c:921:1: warning: label ‘__ats_lab_workshop_make_01695_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘deque_remove_beg_01749_ats_clo_ptr_type’:
binarytrees_dats.c:941:1: warning: label ‘__ats_lab_deque_remove_beg_01749_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘queue_remove_01725_ats_clo_ptr_type’:
binarytrees_dats.c:963:1: warning: label ‘__ats_lab_queue_remove_01725_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘workshop_remove_work_01703_ats_clo_ptr_type’:
binarytrees_dats.c:1041:1: warning: label ‘__ats_lab_workshop_remove_work_01703_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘worker_24’:
binarytrees_dats.c:1140:1: warning: label ‘__ats_lab_11_0’ defined but not used [-Wunused-label]
binarytrees_dats.c:1106:1: warning: label ‘__ats_lab_10_0’ defined but not used [-Wunused-label]
binarytrees_dats.c:1098:1: warning: label ‘__ats_lab_9_1’ defined but not used [-Wunused-label]
binarytrees_dats.c:1097:1: warning: label ‘__ats_lab_9_0’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘workshop_add_worker_01700_ats_clo_ptr_type’:
binarytrees_dats.c:1184:1: warning: label ‘__ats_lab_workshop_add_worker_01700_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘workshop_add_nworker_01701_ats_clo_ptr_type’:
binarytrees_dats.c:1237:1: warning: label ‘__ats_lab_workshop_add_nworker_01701_ats_clo_ptr_type’ defined but not used [-Wunused-label]
binarytrees_dats.c: In function ‘mainats’:
binarytrees_dats.c:1327:1: warning: label ‘__ats_lab_13’ defined but not used [-Wunused-label]
binarytrees_dats.c:1285:1: warning: label ‘__ats_lab_mainats’ defined but not used [-Wunused-label]
In file included from binarytrees_dats.c:29:0:
binarytrees_dats.c: At top level:
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/pointer.cats:52:14: warning: ‘atspre_null_ptr’ defined but not used [-Wunused-variable]
In file included from binarytrees_dats.c:30:0:
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/printf.cats:57:1: warning: ‘atspre_fprintf_err’ defined but not used [-Wunused-function]
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/printf.cats:69:1: warning: ‘atspre_fprintf_exn’ defined but not used [-Wunused-function]
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/printf.cats:105:1: warning: ‘atspre_prerrf_exn’ defined but not used [-Wunused-function]
In file included from binarytrees_dats.c:33:0:
/usr/local/src/ats-lang-anairiats-0.2.9/prelude/CATS/string.cats:351:14: warning: ‘atspre_stropt_none’ defined but not used [-Wunused-variable]
binarytrees_dats.c:532:1: warning: ‘loop_8_closure_make’ defined but not used [-Wunused-function]
gcc -I/usr/local/src/ats-lang-anairiats-0.2.9/ -I/usr/local/src/ats-lang-anairiats-0.2.9/ccomp/runtime/ -L/usr/local/src/ats-lang-anairiats-0.2.9/ccomp/lib/ /usr/local/src/ats-lang-anairiats-0.2.9/ccomp/runtime/ats_prelude.c -D_GNU_SOURCE -D_ATS_MULTITHREAD -D_ATS_GCATS -lpthread -pipe -Wall -O3 -fomit-frame-pointer -march=native binarytrees_dats.c -o binarytrees.ats-3.ats_run /usr/local/src/ats-lang-anairiats-0.2.9/ccomp/runtime/GCATS/gc_mt.o -lats_mt -lats 
0.61s to complete and log all make actions

COMMAND LINE:
./binarytrees.ats-3.ats_run 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1

  Home   Conclusions   License   Play