From cd739cd028e303b29d9ac997dd4af421fa05654b Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 16 Oct 2009 10:11:31 +0000 Subject: [PATCH] more benchmark --- .../src/Benchmarks/SingleTM/Yada/element.java | 30 +-- Robust/src/Benchmarks/SingleTM/Yada/heap.java | 228 ++++++++++++++++++ .../src/Benchmarks/SingleTM/Yada/region.java | 2 +- Robust/src/Benchmarks/SingleTM/Yada/yada.java | 6 +- 4 files changed, 247 insertions(+), 19 deletions(-) create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/heap.java diff --git a/Robust/src/Benchmarks/SingleTM/Yada/element.java b/Robust/src/Benchmarks/SingleTM/Yada/element.java index a7dc9067..5ec24c5a 100644 --- a/Robust/src/Benchmarks/SingleTM/Yada/element.java +++ b/Robust/src/Benchmarks/SingleTM/Yada/element.java @@ -296,9 +296,9 @@ int element_compare (element aElementPtr, element bElementPtr) { * For use in list_t * ============================================================================= */ - int element_listCompare (const void* aPtr, const void* bPtr) { - element_t* aElementPtr = (element_t*)aPtr; - element_t* bElementPtr = (element_t*)bPtr; + int element_listCompare (Object aPtr, Object bPtr) { + element aElementPtr = (element)aPtr; + element bElementPtr = (element)bPtr; return element_compare(aElementPtr, bElementPtr); } @@ -310,9 +310,9 @@ int element_compare (element aElementPtr, element bElementPtr) { * For use in MAP_T * ============================================================================= */ - int element_mapCompare (const pair_t* aPtr, const pair_t* bPtr) { - element_t* aElementPtr = (element_t*)(aPtr->firstPtr); - element_t* bElementPtr = (element_t*)(bPtr->firstPtr); + int element_mapCompare(Object aPtr, Object bPtr) { + element aElementPtr = (element)(aPtr.firstPtr); + element bElementPtr = (element)(bPtr.firstPtr); return element_compare(aElementPtr, bElementPtr); } @@ -367,8 +367,8 @@ int element_compare (element aElementPtr, element bElementPtr) { * ============================================================================= */ static int compareEdge(edge aEdgePtr, edge bEdgePtr) { - int diffFirst = coordinate_compare((coordinate_t*)aEdgePtr.firstPtr, - (coordinate_t*)bEdgePtr.firstPtr); + int diffFirst = coordinate_compare((coordinate)aEdgePtr.firstPtr, + (coordinate)bEdgePtr.firstPtr); return ((diffFirst != 0) ? (diffFirst) : @@ -397,9 +397,9 @@ int element_compare (element aElementPtr, element bElementPtr) { * For use in MAP_T * ============================================================================= */ - int element_mapCompareEdge (const pair_t* aPtr, const pair_t* bPtr) { - edge_t* aEdgePtr = (edge_t*)(aPtr.firstPtr); - edge_t* bEdgePtr = (edge_t*)(bPtr.firstPtr); + int element_mapCompareEdge (Object aPtr, Object bPtr) { + edge aEdgePtr = (edge)(aPtr.firstPtr); + edge bEdgePtr = (edge)(bPtr.firstPtr); return compareEdge(aEdgePtr, bEdgePtr); } @@ -411,10 +411,10 @@ int element_compare (element aElementPtr, element bElementPtr) { * For use in heap_t. Consider using minAngle instead of "do not care". * ============================================================================= */ - int element_heapCompare (const void* aPtr, const void* bPtr) { - element_t* aElementPtr = (element_t*)aPtr; - element_t* bElementPtr = (element_t*)bPtr; - + int element_heapCompare (Object aPtr, Object bPtr) { + element aElementPtr = (element)aPtr; + element bElementPtr = (element)bPtr; + if (aElementPtr.encroachedEdgePtr) { if (bElementPtr.encroachedEdgePtr) { return 0; /* do not care */ diff --git a/Robust/src/Benchmarks/SingleTM/Yada/heap.java b/Robust/src/Benchmarks/SingleTM/Yada/heap.java new file mode 100644 index 00000000..5e00ce3b --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/heap.java @@ -0,0 +1,228 @@ +/* ============================================================================= + * + * heap.c + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of kmeans, please see kmeans/LICENSE.kmeans + * + * ------------------------------------------------------------------------ + * + * For the license of ssca2, please see ssca2/COPYRIGHT + * + * ------------------------------------------------------------------------ + * + * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the + * header of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of lib/rbtree.h and lib/rbtree.c, please see + * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford University nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + * + * ============================================================================= + */ + +#define PARENT(i) ((i) / 2) +#define LEFT_CHILD(i) (2*i) +#define RIGHT_CHILD(i) (2*(i) + 1) + +public class heap { + Object [] elements; + int size; + int capacity; + +/* ============================================================================= + * heap_alloc + * -- Returns NULL on failure + * ============================================================================= + */ + public heap(int initCapacity) { + int capacity = ((initCapacity > 0) ? (initCapacity) : (1)); + elements = new Object[capacity]; + size=0; + this.capacity = capacity; + } + +/* ============================================================================= + * siftUp + * ============================================================================= + */ + public void siftUp(long startIndex) { + long index = startIndex; + while ((index > 1)) { + long parentIndex = PARENT(index); + Object parentPtr = elements[parentIndex]; + Object thisPtr = elements[index]; + if (compare(parentPtr, thisPtr) >= 0) { + break; + } + Object tmpPtr = parentPtr; + elements[parentIndex] = thisPtr; + elements[index] = tmpPtr; + index = parentIndex; + } + } + +/* ============================================================================= + * heap_insert + * -- Returns FALSE on failure + * ============================================================================= + */ + public boolean heap_insert(Object dataPtr) { + if ((size + 1) >= capacity) { + long newCapacity = capacity * 2; + Object newElements[] = new Object[newCapacity]; + this.capacity = newCapacity; + for (int i = 0; i <= size; i++) { + newElements[i] = elements[i]; + } + this.elements = newElements; + } + + size++; + elements[size] = dataPtr; + siftUp(heapPtr, size); + + return true; + } + + +/* ============================================================================= + * heapify + * ============================================================================= + */ + public void heapify(int startIndex) { + int index = startIndex; + + while (true) { + int leftIndex = LEFT_CHILD(index); + int rightIndex = RIGHT_CHILD(index); + int maxIndex = -1; + + if ((leftIndex <= size) && + (compare(elements[leftIndex], elements[index]) > 0)) { + maxIndex = leftIndex; + } else { + maxIndex = index; + } + + if ((rightIndex <= size) && + (compare(elements[rightIndex], elements[maxIndex]) > 0)) { + maxIndex = rightIndex; + } + + if (maxIndex == index) { + break; + } else { + Object tmpPtr = elements[index]; + elements[index] = elements[maxIndex]; + elements[maxIndex] = tmpPtr; + index = maxIndex; + } + } + } + + +/* ============================================================================= + * heap_remove + * -- Returns NULL if empty + * ============================================================================= + */ + Object heap_remove() { + if (size < 1) { + return null; + } + + Object dataPtr = elements[1]; + elements[1] = elements[size]; + size--; + heapify(1); + + return dataPtr; + } + +/* ============================================================================= + * heap_isValid + * ============================================================================= + */ + boolean heap_isValid() { + for (int i = 1; i < size; i++) { + if (compare(elements[i+1], elements[PARENT(i+1)]) > 0) { + return false; + } + } + return true; + } + + + private static int compare(Object aPtr, Object bPtr) { + element aElementPtr = (element)aPtr; + element bElementPtr = (element)bPtr; + + if (aElementPtr.encroachedEdgePtr) { + if (bElementPtr.encroachedEdgePtr) { + return 0; /* do not care */ + } else { + return 1; + } + } + + if (bElementPtr.encroachedEdgePtr) { + return -1; + } + } + + public void printHeap() { + System.out.println("["); + for (int i = 0; i < size; i++) { + System.out.print(elements[i+1]+" "); + } + System.out.println("]"); + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Yada/region.java b/Robust/src/Benchmarks/SingleTM/Yada/region.java index 352272e7..4eef55dc 100644 --- a/Robust/src/Benchmarks/SingleTM/Yada/region.java +++ b/Robust/src/Benchmarks/SingleTM/Yada/region.java @@ -323,7 +323,7 @@ public class region { element badElementPtr = (element)badVectorPtr.vector_at(i); if (badElementPtr.element_isGarbage()) { } else { - boolean status = TMHEAP_INSERT(workHeapPtr, (void*)badElementPtr); + boolean status = workHeapPtr.heap_insert(badElementPtr); assert(status); } } diff --git a/Robust/src/Benchmarks/SingleTM/Yada/yada.java b/Robust/src/Benchmarks/SingleTM/Yada/yada.java index 1f051fca..f5593bc1 100644 --- a/Robust/src/Benchmarks/SingleTM/Yada/yada.java +++ b/Robust/src/Benchmarks/SingleTM/Yada/yada.java @@ -54,7 +54,7 @@ public class yada { int global_numThread; double global_angleConstraint; mesh global_meshPtr; - heap_t global_workHeapPtr; + heap global_workHeapPtr; int global_totalNumAdded; int global_numProcess; @@ -146,7 +146,7 @@ public class yada { while (true) { element elementPtr; atomic { - elementPtr = TMHEAP_REMOVE(workHeapPtr); + elementPtr = (element) workHeapPtr.heap_remove(); } if (elementPtr == null) { break; @@ -206,7 +206,7 @@ public class yada { System.out.println("Reading input... "); int initNumElement = global_meshPtr.mesh_read(global_inputPrefix); System.out.println("done."); - y.global_workHeapPtr = new heap(1, &element_heapCompare); + y.global_workHeapPtr = new heap(1); int initNumBadElement = global_workHeapPtr.initializeWork(global_meshPtr); -- 2.34.1