NOTE: This patch has been committed. The version below is informational only (whitespace differences have been removed). ../ChangeLog addition: 2006-01-09 Didier Verna <didier@lrde.epita.fr> * 2.0/src/dd/eiffel/maini.e: New (randomized access version). * 2.0/src/dd/eiffel/image_mb.e: New (multibuffer image class). * 2.0/src/dd/eiffel/image_sb.e: formerly known as image1d_int.e. * 2.0/src/dd/java/MainI.java: New (randomized access version). * 2.0/src/dd/c/dd_ci.c: See below. * 2.0/src/dd/c/dd_c.c: Ditto. * 2.0/src/dd/eiffel/main.e: Ditto. * 2.0/src/dd/java/Main.java: Ditto. Dedicated versions update: - add 2D array implementations in all languages, - add missing "randomized" versions in all languages, - add command-line arguments for size and steps, - default to 800x800 and 200 steps, - use a prime number not subject to integer overflow. GSC source patch: Diff command: svn diff --diff-cmd /usr/bin/diff -x "-u -t -b -B -w" Files affected: src/dd/eiffel/image_sb.e src/dd/eiffel/main.e src/dd/eiffel/image_mb.e src/dd/eiffel/maini.e src/dd/c/dd_c.c src/dd/c/dd_ci.c src/dd/java/MainI.java src/dd/java/Main.java Index: src/dd/java/Main.java =================================================================== --- src/dd/java/Main.java (revision 42) +++ src/dd/java/Main.java (working copy) @@ -1,15 +1,14 @@ - // compile and run with: // javac Main.java -// java -cp . Main +// java Main import java.io.*; import java.util.Timer; -class Image2d_int +class ImageSB { - public Image2d_int(int n) + public ImageSB(int n) { this.n = n; data = new int[n]; @@ -18,37 +17,71 @@ public int[] data; } +class ImageMB +{ + public ImageMB(int n) + { + this.n = n; + data = new int[n][n]; + } + public int n; + public int[][] data; +} + class Main { - public static void assign(Image2d_int ima, int val) + public static void assignSB(ImageSB ima, int val) { int n = ima.n; for (int i = 0; i < n; ++i) ima.data[i] = val; } + public static void assignMB(ImageMB ima, int val) + { + int n = ima.n; + for (int i = 0; i < n; ++i) + for (int j = 0; j < n; ++j) + ima.data[i][j] = val; + } + public static void usage() { - System.err.println("usage: java Main [nsteps = 1]"); + System.err.println("usage: java Main [size = 800] [nsteps = 200]"); } public static void main(String[] args) { - if (args.length > 1) + if (args.length > 2) { usage(); return; } - int nsteps = args.length == 0 ? 1 : Integer.parseInt(args[0]); - int size = 1024 * 1024; - Image2d_int ima = new Image2d_int(size); + int size = args.length > 0 ? Integer.parseInt(args[0]) : 800; + int nsteps = args.length > 1 ? Integer.parseInt(args[1]) : 200; int val = 51; + System.out.println("Linear / " + + size + "x" + size + " / " + + nsteps + " steps:"); + + { + ImageSB ima = new ImageSB(size * size); long t0 = System.currentTimeMillis(); for (int step = 0; step < nsteps; ++step) - assign(ima, val); - System.out.println((System.currentTimeMillis() - t0)/(double)1000); + assignSB(ima, val); + long t1 = System.currentTimeMillis(); + System.out.println("SB: " + (t1 - t0)/(double)1000); + } + { + ImageMB ima = new ImageMB(size); + long t0 = System.currentTimeMillis(); + for (int step = 0; step < nsteps; ++step) + assignMB(ima, val); + long t1 = System.currentTimeMillis(); + System.out.println("MB: " + (t1 - t0)/(double)1000); + } } } Index: src/dd/java/MainI.java =================================================================== --- src/dd/java/MainI.java (revision 0) +++ src/dd/java/MainI.java (revision 0) @@ -0,0 +1,103 @@ +// compile and run with: +// javac MainI.java +// java MainI + +import java.io.*; +import java.util.Timer; + + +class ImageSBI +{ + public ImageSBI(int n) + { + this.n = n; + data = new int[n]; + } + public int n; + public int[] data; +} + +class ImageMBI +{ + public ImageMBI(int n) + { + this.n = n; + data = new int[n][n]; + } + public int n; + public int[][] data; +} + + + +class MainI +{ + public static void assignSB(ImageSBI ima, int val) + { + int n = ima.n, offset = 0; + + for (int i = 0; i < n; ++i) + { + offset += MainI.offset; + ima.data[offset % n] = val; + } + } + + public static void assignMB(ImageMBI ima, int val) + { + int n = ima.n, offset_i, offset_j = 0; + + for (int j = 0; j < n; ++j) + { + offset_j += MainI.offset; + offset_i = 0; + + for (int i = 0; i < n; ++i) + { + offset_i += MainI.offset; + ima.data[offset_i % n][offset_j % n] = val; + } + } + } + + public static void usage() + { + System.err.println("usage: java MainI [size = 800] [nsteps = 200]"); + } + + public static void main(String[] args) + { + if (args.length > 2) + { + usage(); + return; + } + int size = args.length > 0 ? Integer.parseInt(args[0]) : 800; + int nsteps = args.length > 1 ? Integer.parseInt(args[1]) : 200; + int val = 51; + + System.out.println("Randomized / " + + size + "x" + size + " / " + + nsteps + " steps:"); + + { + ImageSBI ima = new ImageSBI(size * size); + long t0 = System.currentTimeMillis(); + for (int step = 0; step < nsteps; ++step) + assignSB(ima, val); + long t1 = System.currentTimeMillis(); + System.out.println("SB: " + (t1 - t0)/(double)1000); + } + { + ImageMBI ima = new ImageMBI(size); + long t0 = System.currentTimeMillis(); + for (int step = 0; step < nsteps; ++step) + assignMB(ima, val); + long t1 = System.currentTimeMillis(); + System.out.println("MB: " + (t1 - t0)/(double)1000); + } + } + + // see comment in file ../cl/ti.cl + public static int offset = 509; +} Index: src/dd/c/dd_ci.c =================================================================== --- src/dd/c/dd_ci.c (revision 42) +++ src/dd/c/dd_ci.c (working copy) @@ -2,37 +2,129 @@ #include <stdlib.h> #include <time.h> - +/* see comment in file ../cl/ti.cl */ +#define OFFSET 509 typedef struct { - unsigned n; + int n; int* data; } -image1d_int; + image_sb; + +typedef struct +{ + int n; + int** data; +} + image_mb; + + + +image_sb* new_image_sb (int n) +{ + image_sb* ima; + + ima = (image_sb*) malloc (sizeof (image_sb)); + if (ima == NULL) + { + perror ("malloc"); + exit (1); + } + + ima->n = n; + + ima->data = (int*) calloc (n, sizeof (int)); + if (ima->data == NULL) + { + perror ("calloc"); + exit (1); + } + + return ima; +} + +void free_image_sb (image_sb* ima) +{ + free (ima->data); + free (ima); +} + + +image_mb* new_image_mb (int n) +{ + image_mb* ima; + int i; + + ima = (image_mb*) malloc (sizeof (image_mb)); + if (ima == NULL) + { + perror ("malloc"); + exit (1); + } + ima->n = n; + ima->data = (int**) calloc (n, sizeof (int*)); + if (ima->data == NULL) + { + perror ("calloc"); + exit (1); + } -image1d_int* new_image1d_int(unsigned n) + for (i = 0; i < n; ++i) { - image1d_int* this; - this = (image1d_int*)malloc(1 * sizeof(image1d_int)); - this->n = n; - this->data = (int*)malloc(n * sizeof(int)); - return this; + ima->data[i] = (int*) calloc (n, sizeof (int)); + if (ima->data[i] == NULL) + { + perror ("calloc"); + exit (1); } + } + + return ima; +} + +void free_image_mb (image_mb* ima) +{ + int i; + const int n = ima->n; + + for (i = 0; i < n; ++i) + free (ima->data[i]); + free (ima->data); + free (ima); +} + +void assign_sb (image_sb* ima, int val) +{ + int i, offset = 0; + const int n = ima->n; + + for (i = 0; i < n; ++i) + { + offset += OFFSET; + ima->data[offset % n] = val; + } +} +void assign_mb (image_mb* ima, int val) +{ + int i, j, offset_i, offset_j = 0; + const int n = ima->n; -void assign(image1d_int* ima, int val) + for (j = 0; j < n; ++j) { - unsigned i, offset = 0; - const unsigned n = ima->n; - int* p = ima->data; + offset_j += OFFSET; + offset_i = 0; + for (i = 0; i < n; ++i) { - offset += 999983; - *(p + offset % n) = val; + offset_i += OFFSET; + + ima->data[offset_i % n][offset_j % n] = val; + } } } @@ -40,30 +132,41 @@ void usage(char* argv[]) { - printf("usage: %s [size = 1024] [nsteps = 1]\n", argv[0]); + printf ("usage: %s [size = 800] [nsteps = 200]\n", argv[0]); exit(1); } int main(int argc, char* argv[]) { - image1d_int* ima; - unsigned size, step, nsteps; + image_sb* ima_sb; + image_mb* ima_mb; + int size, step, nsteps; float t0; int val; - int i = 0; if (argc > 3) usage(argv); - size = argc > 1 ? atoi(argv[1]) : 1024; - nsteps = argc > 2 ? atoi(argv[2]) : 1; + size = argc > 1 ? atoi (argv[1]) : 800; + nsteps = argc > 2 ? atoi (argv[2]) : 200; - ima = new_image1d_int(size * size); val = 51; + printf ("Randomized / %dx%d / %d steps:\n", size, size, nsteps); + + ima_sb = new_image_sb (size * size); t0 = (float)clock(); for (step = 0; step < nsteps; ++step) - assign(ima, val); - printf("%f\n", (clock() - t0) / CLOCKS_PER_SEC); + assign_sb (ima_sb, val); + printf ("SB: %f\n", (clock() - t0) / CLOCKS_PER_SEC); + free_image_sb (ima_sb); + + ima_mb = new_image_mb (size); + t0 = (float) clock (); + for (step = 0; step < nsteps; ++step) + assign_mb (ima_mb, val); + printf ("MB: %f\n", (clock() - t0) / CLOCKS_PER_SEC); + free_image_mb (ima_mb); + return 0; } Index: src/dd/c/dd_c.c =================================================================== --- src/dd/c/dd_c.c (revision 42) +++ src/dd/c/dd_c.c (working copy) @@ -6,60 +6,154 @@ typedef struct { - unsigned n; + int n; int* data; } -image1d_int; + image_sb; + +typedef struct +{ + int n; + int** data; +} + image_mb; -image1d_int* new_image1d_int(unsigned n) +image_sb* new_image_sb (int n) { - image1d_int* this; - this = (image1d_int*)malloc(1 * sizeof(image1d_int)); - this->n = n; - this->data = (int*)malloc(n * sizeof(int)); - return this; + image_sb* ima; + + ima = (image_sb*) malloc (sizeof (image_sb)); + if (ima == NULL) + { + perror ("malloc"); + exit (1); } + ima->n = n; + ima->data = (int*) calloc (n, sizeof (int)); + if (ima->data == NULL) + { + perror ("calloc"); + exit (1); + } -void assign(image1d_int* ima, int val) + return ima; +} + +void free_image_sb (image_sb* ima) { - unsigned i; - const unsigned n = ima->n; - int* p = ima->data; + free (ima->data); + free (ima); +} + + +image_mb* new_image_mb (int n) +{ + image_mb* ima; + int i; + + ima = (image_mb*) malloc (sizeof (image_mb)); + if (ima == NULL) + { + perror ("malloc"); + exit (1); + } + + ima->n = n; + + ima->data = (int**) calloc (n, sizeof (int*)); + if (ima->data == NULL) + { + perror ("calloc"); + exit (1); + } + for (i = 0; i < n; ++i) - *p++ = val; + { + ima->data[i] = (int*) calloc (n, sizeof (int)); + if (ima->data[i] == NULL) + { + perror ("calloc"); + exit (1); + } + } + + return ima; +} + +void free_image_mb (image_mb* ima) +{ + int i; + const int n = ima->n; + + for (i = 0; i < n; ++i) + free (ima->data[i]); + free (ima->data); + free (ima); +} + + +void assign_sb (image_sb* ima, int val) +{ + int i; + const int n = ima->n; + + for (i = 0; i < n; ++i) + ima->data[i] = val; +} + +void assign_mb (image_mb* ima, int val) +{ + int i, j; + const int n = ima->n; + + for (i = 0; i < n; ++i) + for (j = 0; j < n; ++j) + ima->data[i][j] = val; } void usage(char* argv[]) { - printf("usage: %s [nsteps = 1]\n", argv[0]); + printf ("usage: %s [size = 800] [nsteps = 200]\n", argv[0]); exit(1); } int main(int argc, char* argv[]) { - image1d_int* ima; - const unsigned size = 1024 * 1024; - unsigned step, nsteps; + image_sb* ima_sb; + image_mb* ima_mb; + int size, step, nsteps; float t0; int val; - if (argc > 2) + if (argc > 3) usage(argv); - nsteps = argc == 2 ? atoi(argv[1]) : 1; + size = argc > 1 ? atoi (argv[1]) : 800; + nsteps = argc > 2 ? atoi (argv[2]) : 200; - ima = new_image1d_int(size); val = 51; + printf ("Linear / %dx%d / %d steps:\n", size, size, nsteps); + + ima_sb = new_image_sb (size * size); + t0 = (float) clock (); + for (step = 0; step < nsteps; ++step) + assign_sb (ima_sb, val); + printf ("SB: %f\n", (clock() - t0) / CLOCKS_PER_SEC); + free_image_sb (ima_sb); + + ima_mb = new_image_mb (size); t0 = (float)clock(); for (step = 0; step < nsteps; ++step) - assign(ima, val); - printf("%f\n", (clock() - t0) / CLOCKS_PER_SEC); + assign_mb (ima_mb, val); + printf ("MB: %f\n", (clock() - t0) / CLOCKS_PER_SEC); + free_image_mb (ima_mb); + return 0; } Index: src/dd/eiffel/maini.e =================================================================== --- src/dd/eiffel/maini.e (revision 0) +++ src/dd/eiffel/maini.e (revision 0) @@ -0,0 +1,117 @@ +class MAINI + +creation + make + +feature + + offset : INTEGER + + make is + local + ima_sb : IMAGE_SB + ima_mb : IMAGE_MB + val : INTEGER + size, step, nsteps : INTEGER + t0, t : MICROSECOND_TIME + do + if argument_count > 2 then + io.put_string("usage : exec [size = 800] [nsteps = 200]%N") + else + if argument_count > 0 then + size := argument(1).to_integer + else + size := 800; + end + if argument_count > 1 then + nsteps := argument(2).to_integer + else + nsteps := 200 + end + + val := 51 + -- See comment in ../cl/ti.cl + offset := 509 + + print("Randomized / " + + size.to_string + "x" + size.to_string + " / " + + nsteps.to_string + " steps:%N") + + create ima_sb.make(size * size) + t0.update + from + step := 1 + until + step > nsteps + loop + assign_sb(ima_sb, val) + step := step + 1 + end + t.update + print("SB: " + (t0.elapsed_seconds(t)).to_string + "%N") + + create ima_mb.make(size) + t0.update + from + step := 1 + until + step > nsteps + loop + assign_mb(ima_mb, val) + step := step + 1 + end + t.update + print("MB: " + (t0.elapsed_seconds(t)).to_string + "%N") + end + end + + assign_sb(ima : IMAGE_SB; val : INTEGER) is + local + i : INTEGER + the_offset : INTEGER + n : INTEGER + do + the_offset := 0 + n := ima.n + from + i := 0 + until + i >= n + loop + the_offset := the_offset + offset + ima.data.put(val, the_offset \\ n) + i := i + 1 + end + end + + assign_mb(ima : IMAGE_MB; val : INTEGER) is + local + i : INTEGER + j : INTEGER + offset_i : INTEGER + offset_j : INTEGER + n : INTEGER + do + n := ima.n + offset_j := 0 + from + j := 0 + until + j >= ima.n + loop + offset_j := offset_j + offset + offset_i := 0 + from + i := 0 + until + i >= ima.n + loop + offset_i := offset_i + offset + ima.data.put(val, offset_i \\ n, offset_j \\ n) + i := i + 1 + end + j := j + 1 + end + end + +end -- MAINI Index: src/dd/eiffel/image_mb.e =================================================================== --- src/dd/eiffel/image_mb.e (revision 0) +++ src/dd/eiffel/image_mb.e (revision 0) @@ -0,0 +1,16 @@ +class IMAGE_MB + +create make + +feature + + n : INTEGER + data : ARRAY2[INTEGER] + + make(n_ : INTEGER) is + do + n := n_ + create data.make(0, n_, 0, n_) + end + +end -- IMAGE_MB Index: src/dd/eiffel/main.e =================================================================== --- src/dd/eiffel/main.e (revision 42) +++ src/dd/eiffel/main.e (working copy) @@ -8,38 +7,61 @@ make is local - ima : IMAGE1D_INT + ima_sb : IMAGE_SB + ima_mb : IMAGE_MB val : INTEGER size, step, nsteps : INTEGER - t0, t : TIME + t0, t : MICROSECOND_TIME do - size := 1024 * 1024 - if argument_count /= 0 and argument_count /= 1 then - io.put_string("usage : exec [nsteps = 1]%N") + if argument_count > 2 then + io.put_string("usage : exec [size = 800] [nsteps = 200]%N") + else + if argument_count > 0 then + size := argument(1).to_integer else - if argument_count = 0 then - nsteps := 1 - elseif argument_count = 1 then - nsteps := argument(1).to_integer + size := 800; end - create ima.make(size) + if argument_count > 1 then + nsteps := argument(2).to_integer + else + nsteps := 200 + end + val := 51 + + print("Linear / " + + size.to_string + "x" + size.to_string + " / " + + nsteps.to_string + " steps:%N") + + create ima_sb.make(size * size) + t0.update + from + step := 1 + until + step > nsteps + loop + assign_sb(ima_sb, val) + step := step + 1 + end + t.update + print("SB: " + (t0.elapsed_seconds(t)).to_string + "%N") + + create ima_mb.make(size) t0.update from step := 1 until step > nsteps loop - assign(ima, val) + assign_mb(ima_mb, val) step := step + 1 end t.update - print(t0.elapsed_seconds(t)) - print("%N") + print("MB: " + (t0.elapsed_seconds(t)).to_string + "%N") end end - assign(ima : IMAGE1D_INT; val : INTEGER) is + assign_sb(ima : IMAGE_SB; val : INTEGER) is local i : INTEGER do @@ -53,4 +75,26 @@ end end + assign_mb(ima : IMAGE_MB; val : INTEGER) is + local + i : INTEGER + j : INTEGER + do + from + i := 0 + until + i >= ima.n + loop + from + j := 0 + until + j >= ima.n + loop + ima.data.put(val, i, j) + j := j + 1 + end + i := i + 1 + end + end + end -- MAIN Index: src/dd/eiffel/image_sb.e =================================================================== --- src/dd/eiffel/image_sb.e (revision 0) +++ src/dd/eiffel/image_sb.e (revision 0) @@ -0,0 +1,16 @@ +class IMAGE_SB + +create make + +feature + + n : INTEGER + data : ARRAY[INTEGER] + + make(n_ : INTEGER) is + do + n := n_ + create data.make(0, n_) + end + +end -- IMAGE_SB -- Didier Verna, didier@lrde.epita.fr, http://www.lrde.epita.fr/~didier EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (1) 44 08 01 85 94276 Le Kremlin-Bicêtre, France Fax.+33 (1) 53 14 59 22 didier@xemacs.org