Thread: [Nice-commit] Nice/src/mlsub/typing/lowlevel BitVector.java,1.5,1.6 Interface.java,1.3,1.4 K0.java,1
Brought to you by:
bonniot
Menu
▾
▴
nice-commit
|
From: <ar...@us...> - 2003-06-26 10:37:17
|
Update of /cvsroot/nice/Nice/src/mlsub/typing/lowlevel
In directory sc8-pr-cvs1:/tmp/cvs-serv20124/F:/nice/src/mlsub/typing/lowlevel
Modified Files:
BitVector.java Interface.java K0.java
Log Message:
Another round of optimizations for typing.lowlevel .
Index: BitVector.java
===================================================================
RCS file: /cvsroot/nice/Nice/src/mlsub/typing/lowlevel/BitVector.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** BitVector.java 6 Apr 2003 19:00:18 -0000 1.5
--- BitVector.java 26 Jun 2003 10:37:13 -0000 1.6
***************
*** 25,29 ****
@return number of WORDS allocated
*/
! private int length()
{
if (bits1 == null)
--- 25,29 ----
@return number of WORDS allocated
*/
! final private int length()
{
if (bits1 == null)
***************
*** 36,40 ****
* Convert bitIndex to a subscript into the bits[] array.
*/
! private static int subscript(int bitIndex) {
return bitIndex >> BITS_PER_UNIT;
}
--- 36,40 ----
* Convert bitIndex to a subscript into the bits[] array.
*/
! final private static int subscript(int bitIndex) {
return bitIndex >> BITS_PER_UNIT;
}
***************
*** 42,46 ****
* Convert a subscript into the bits[] array to a (maximum) bitIndex.
*/
! private static int bitIndex(int subscript) {
return (subscript << BITS_PER_UNIT) + MASK;
}
--- 42,46 ----
* Convert a subscript into the bits[] array to a (maximum) bitIndex.
*/
! final private static int bitIndex(int subscript) {
return (subscript << BITS_PER_UNIT) + MASK;
}
***************
*** 50,54 ****
*/
public BitVector() {
! this(1 << BITS_PER_UNIT);
}
--- 50,55 ----
*/
public BitVector() {
! bits0 = 0L;
! bits1 = null;
}
***************
*** 86,90 ****
* @param nth the 0-origin number of the bit to ensure is there.
*/
! private void ensureCapacity(int nth) {
int required = subscript(nth) + 1; /* +1 to get length, not index */
if (required == 1)
--- 87,91 ----
* @param nth the 0-origin number of the bit to ensure is there.
*/
! final private void ensureCapacity(int nth) {
int required = subscript(nth) + 1; /* +1 to get length, not index */
if (required == 1)
***************
*** 107,115 ****
}
/**
* Sets a bit.
* @param bit the bit to be set
*/
! public void set(int bit) {
if (bit < 0) {
throw new IndexOutOfBoundsException(Integer.toString(bit));
--- 108,134 ----
}
+ final private void ensureChunkCapacity(int required) {
+ if (required > length()) {
+ /* Ask for larger of doubled size or required size */
+ int request = Math.max(2 * length(), required);
+ if (bits1 == null)
+ {
+ bits1 = new long[request];
+ bits1[0] = bits0;
+ }
+ else
+ {
+ long[] newBits = new long[request];
+ System.arraycopy(bits1, 0, newBits, 0, bits1.length);
+ bits1 = newBits;
+ }
+ }
+ }
+
/**
* Sets a bit.
* @param bit the bit to be set
*/
! final public void set(int bit) {
if (bit < 0) {
throw new IndexOutOfBoundsException(Integer.toString(bit));
***************
*** 130,138 ****
throw new IndexOutOfBoundsException(Integer.toString(bit));
}
! ensureCapacity(bit);
! if (bits1 == null)
! bits0 &= ~(1L << bit); // we know that bit <= 64
! else
! bits1[subscript(bit)] &= ~(1L << (bit & MASK));
}
--- 149,155 ----
throw new IndexOutOfBoundsException(Integer.toString(bit));
}
! int sub = subscript(bit);
! if (sub < length())
! andW(sub, ~(1L << (bit & MASK)));
}
***************
*** 234,238 ****
@return bits[i]
*/
! private long getW(int i)
{
if (bits1 == null)
--- 251,255 ----
@return bits[i]
*/
! final private long getW(int i)
{
if (bits1 == null)
***************
*** 247,251 ****
Assumes i is a valid word index.
*/
! private void setW(int i, long w)
{
if (bits1 == null)
--- 264,268 ----
Assumes i is a valid word index.
*/
! final private void setW(int i, long w)
{
if (bits1 == null)
***************
*** 260,264 ****
Assumes i is a valid word index.
*/
! private void andW(int i, long w)
{
if (bits1 == null)
--- 277,281 ----
Assumes i is a valid word index.
*/
! final private void andW(int i, long w)
{
if (bits1 == null)
***************
*** 273,277 ****
Assumes i is a valid word index.
*/
! private void orW(int i, long w)
{
if (bits1 == null)
--- 290,294 ----
Assumes i is a valid word index.
*/
! final private void orW(int i, long w)
{
if (bits1 == null)
***************
*** 286,290 ****
Assumes i is a valid word index.
*/
! private void xorW(int i, long w)
{
if (bits1 == null)
--- 303,307 ----
Assumes i is a valid word index.
*/
! final private void xorW(int i, long w)
{
if (bits1 == null)
***************
*** 383,392 ****
**/
final public void or(BitVector set) {
! if (this == set) {
! return;
! }
! int setLength = set.nonZeroLength();
if (setLength > 1) {
! ensureCapacity(bitIndex(setLength-1));
for (int i = setLength; i-- > 0 ;) {
bits1[i] |= set.bits1[i];
--- 400,406 ----
**/
final public void or(BitVector set) {
! int setLength = set.length();
if (setLength > 1) {
! ensureChunkCapacity(setLength);
for (int i = setLength; i-- > 0 ;) {
bits1[i] |= set.bits1[i];
***************
*** 400,434 ****
/**
- * Do this = this | (set1 & ~set2)
- **/
- final public void orNotIn(BitVector set1, BitVector set2) {
- if (this == set1) {
- return;
- }
- int set1Length = set1.nonZeroLength();
- int set2Length = set2.length();
- if (set1Length > 0) {
- ensureCapacity(bitIndex(set1Length - 1)); // XXX: problem ?
- }
- for (int i = set1Length; i-- > 0;) {
- if (i < set2Length) {
- orW(i, set1.getW(i) & ~set2.getW(i));
- } else {
- orW(i, set1.getW(i));
- }
- }
- }
-
-
- /**
* Do this = this | (set1 & set2)
**/
final public void orAnd(BitVector set1, BitVector set2) {
- if (this == set1 || this == set2) {
- return;
- }
int setLength = Math.min(set1.nonZeroLength(),set2.nonZeroLength());
! if (setLength > 0) {
! ensureCapacity(bitIndex(setLength-1));// this might cause some problem...
}
for (int i = setLength; i-- > 0 ;) {
--- 414,423 ----
/**
* Do this = this | (set1 & set2)
**/
final public void orAnd(BitVector set1, BitVector set2) {
int setLength = Math.min(set1.nonZeroLength(),set2.nonZeroLength());
! if (setLength > 1) {
! ensureChunkCapacity(setLength);
}
for (int i = setLength; i-- > 0 ;) {
***************
*** 437,456 ****
}
-
-
/*
* If there are some trailing zeros, don't count them
* result is greater or equal to 1
*/
! private int nonZeroLength() {
if (bits1 == null)
return 1;
! int n = bits1.length;
! while (n > 1 && bits1[n-1] == 0L) { n--; }
! return n;
}
-
/**
* Do this = this ^ set
--- 426,442 ----
}
/*
* If there are some trailing zeros, don't count them
* result is greater or equal to 1
*/
! final private int nonZeroLength() {
if (bits1 == null)
return 1;
! int n = bits1.length-1;
! while (n > 0 && bits1[n] == 0L) { n--; }
! return n+1;
}
/**
* Do this = this ^ set
***************
*** 458,463 ****
final public void xor(BitVector set) {
int setLength = set.length();
! if (setLength > 0) {
! ensureCapacity(bitIndex(setLength-1));
}
for (int i = setLength; i-- > 0 ;) {
--- 444,449 ----
final public void xor(BitVector set) {
int setLength = set.length();
! if (setLength > 1) {
! ensureChunkCapacity(setLength);
}
for (int i = setLength; i-- > 0 ;) {
***************
*** 522,527 ****
}
-
-
/**
* Clones the BitVector.
--- 508,511 ----
***************
*** 613,617 ****
}
! private
static /* XXX: work around Symantec JIT bug: comment static */
int chunkLowestSetBit(long chunk) {
--- 597,601 ----
}
! final private
static /* XXX: work around Symantec JIT bug: comment static */
int chunkLowestSetBit(long chunk) {
***************
*** 633,637 ****
* set is empty.
**/
! final public int getLowestSetBit() {
if (bits1 == null)
{
--- 617,621 ----
* set is empty.
**/
! public int getLowestSetBit() {
if (bits1 == null)
{
***************
*** 700,704 ****
}
-
/**
* Compute the first bit set in this & ~set.
--- 684,687 ----
***************
*** 802,812 ****
**/
public boolean isEmpty() {
! int n = length();
! for (int i = 0; i < n; i++) {
! if (getW(i) != 0L) {
return false;
! }
! }
! return true;
}
--- 785,796 ----
**/
public boolean isEmpty() {
! if (bits1 == null)
! return bits0 == 0L;
!
! for (int i = bits1.length; --i>0; )
! if (bits1[i] != 0L)
return false;
!
! return bits1[0] == 0L;
}
***************
*** 873,877 ****
}
-
/**
* Clears the first n bits of this BitVector
--- 857,860 ----
***************
*** 895,904 ****
final public void addProduct(BitMatrix M, BitVector v) {
int n = M.size();
!
for(int i = v.getLowestSetBit();
i >= 0;
i = v.getLowestSetBit(i+1))
! or(M.getRow(i));
}
final public void slowaddProduct(BitMatrix M, BitVector v) {
int n = M.size();
--- 878,900 ----
final public void addProduct(BitMatrix M, BitVector v) {
int n = M.size();
! ensureCapacity(n);
for(int i = v.getLowestSetBit();
i >= 0;
i = v.getLowestSetBit(i+1))
! {
! BitVector set = M.getRow(i);
! int setLength = set.nonZeroLength();
! if (setLength > 1) {
! for (int j = setLength; j-- > 0 ;)
! bits1[j] |= set.bits1[j];
! }
! else
! {
! orW(0, set.getW(0));
! }
!
! }
}
+
final public void slowaddProduct(BitMatrix M, BitVector v) {
int n = M.size();
Index: Interface.java
===================================================================
RCS file: /cvsroot/nice/Nice/src/mlsub/typing/lowlevel/Interface.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** Interface.java 2 Jun 2003 17:58:27 -0000 1.3
--- Interface.java 26 Jun 2003 10:37:13 -0000 1.4
***************
*** 40,44 ****
// the approximation of each node of the original context
private final IntVect approx = new IntVect(BitVector.UNDEFINED_INDEX);
!
public void setApprox(int node, int approx)
{
--- 40,50 ----
// the approximation of each node of the original context
private final IntVect approx = new IntVect(BitVector.UNDEFINED_INDEX);
! private final BitVector hasapprox = new BitVector();
!
! public BitVector getHasApprox()
! {
! return hasapprox;
! }
!
public void setApprox(int node, int approx)
{
***************
*** 46,49 ****
--- 52,59 ----
this.approx.setSize(node+1, BitVector.UNDEFINED_INDEX);
this.approx.set(node, approx);
+ if (approx == BitVector.UNDEFINED_INDEX)
+ hasapprox.clear(node);
+ else
+ hasapprox.set(node);
}
***************
*** 62,69 ****
--- 72,81 ----
implementors.truncate(n);
approx.setSize(n,BitVector.UNDEFINED_INDEX);
+ hasapprox.truncate(n);
}
void indexMove(int src, int dest) {
implementors.bitCopy(src, dest);
approx.set(dest,approx.get(src));
+ hasapprox.set(dest);
if (k0.isRigid(src)) {
// strange as the relation on the rigid indexes should already be
Index: K0.java
===================================================================
RCS file: /cvsroot/nice/Nice/src/mlsub/typing/lowlevel/K0.java,v
retrieving revision 1.18
retrieving revision 1.19
diff -C2 -d -r1.18 -r1.19
*** K0.java 2 Jun 2003 17:58:26 -0000 1.18
--- K0.java 26 Jun 2003 10:37:13 -0000 1.19
***************
*** 1026,1048 ****
{
changed=false;
!
! for(int iid=0; iid<nInterfaces(); iid++)
{
Interface i=getInterface(iid);
int n1;
! //XXX optim: if we had a BitVector i.hasApprox,
! // this could be faster.
! for(int node=0; node<n; node++)
! if((n1=i.getApprox(node))!=BitVector.UNDEFINED_INDEX)
// node ->_i n1
! for(int p=0; p<n; p++)
// is implementors OK ?
// or should not we compute rigidImplementors first ?
! //XXX optim: use i.implementors.getXXXbit to find p candidates
! if(i.implementors.get(p)
! && leq.get(node,p))
if(this.isRigid(p))
! if(!leq.get(n1,p))
! throw new LowlevelUnsatisfiable
("saturateAbs: there should be "+
indexToString(n1)+" <: "+
--- 1026,1049 ----
{
changed=false;
! int nInt = nInterfaces();
! for(int iid=0; iid<nInt; iid++)
{
Interface i=getInterface(iid);
int n1;
! BitVector hasApprox = i.getHasApprox();
! for(int node=hasApprox.getLowestSetBit();
! node != BitVector.UNDEFINED_INDEX;
! node = hasApprox.getNextBit(node))
! {
// node ->_i n1
! n1=i.getApprox(node);
! for(int p = i.implementors.getLowestSetBit();
! p != BitVector.UNDEFINED_INDEX;
! p = i.implementors.getNextBit(p))
// is implementors OK ?
// or should not we compute rigidImplementors first ?
! if(leq.get(node,p) && !leq.get(n1,p))
if(this.isRigid(p))
! throw new LowlevelUnsatisfiable
("saturateAbs: there should be "+
indexToString(n1)+" <: "+
***************
*** 1051,1068 ****
"interface "+interfaceToString(iid)+"\n"+
this);
- else /* Nothing to do. Cool! */ ;
else
! if(!leq.get(n1,p))
! {
! if(debugK0)
System.err.println("Abs rule applied : "+
indexToString(n1)+" < "+indexToString(p)+
" using "+indexToString(node)+
" for interface "+interfaceToString(iid));
! C .set(n1,p);
! Ct.set(p,n1);
! leq.set(n1,p);
! changed=true;
! }
}
if(changed)
--- 1052,1068 ----
"interface "+interfaceToString(iid)+"\n"+
this);
else
! {
! if(debugK0)
System.err.println("Abs rule applied : "+
indexToString(n1)+" < "+indexToString(p)+
" using "+indexToString(node)+
" for interface "+interfaceToString(iid));
! C .set(n1,p);
! Ct.set(p,n1);
! leq.set(n1,p);
! changed=true;
! }
! }
}
if(changed)
|
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X