TAP_support/ADFirstAidKit/admm.c

b4daa24319 Shre*0001 /*
                0002  * TAPENADE Automatic Differentiation Engine
                0003  * Copyright (C) 1999-2021 Inria
                0004  * See the LICENSE.md file in the project root for more information.
                0005  *
                0006  */
                0007
                0008 #include <stdlib.h>
                0009 #include <stdio.h>
                0010 #include <assert.h>
                0011 #include "admm.h"
                0012
                0013 #include <time.h>
                0014
                0015 /* DEBUGGING AND STATISTICS:
                0016  * -------------------------
                0017  * Compile with -D ADMM_TRACE          to log calls to ADMM
                0018  * Compile with -D ADMM_TIME           to show the total time spent in ADMM
                0019  * Compile with -D ADMM_TIME_SEARCHING to show the total time spent searching in the ADMM table
                0020  * Compile with -D ADMM_COUNTS         to show the numbers of ADMM operations and objects
                0021  * Compile with -D ADMM_LABELS         to add a last label argument  to ADMM calls
                0022  */
                0023
                0024 #ifdef ADMM_COUNTS
                0025 int numberOfRegisterings = 0 ;
                0026 int numberOfUnregisterings = 0 ;
                0027 int numberOfChunks = 0 ;
                0028 int peakNumberOfChunks = 0 ;
                0029 int numberOfRebases = 0 ;
                0030 int numberOfWaitings = 0 ;
                0031 int peakNumberOfWaitings = 0 ;
                0032 #endif
                0033
                0034 #ifdef ADMM_TIME
                0035 double timeSpentInADMM = 0.0 ;
                0036 clock_t startADMMTime, endADMMTime ;
                0037 #endif
                0038
                0039 #ifdef ADMM_TIME_SEARCHING
                0040 double timeSpentSearching = 0.0 ;
                0041 clock_t startSearchTime, endSearchTime ;
                0042 #endif
                0043
                0044 /** Cell of a chained list of void* */
                0045 typedef struct _ADMM_List {
                0046   void* head ;
                0047   struct _ADMM_List* tail ;
                0048 } ADMM_List ;
                0049
                0050 typedef enum {BYBASE, BYOBASE, BYBASEB, BYOBASEB} ADMM_AddrSort ;
                0051
                0052 /** All info about one memory chunk */
                0053 typedef struct {
                0054   // 0:base, 1:obase, 2:baseb, 3:obaseb
                0055   void* bases[4] ;
                0056   int   sizeInBytes ;
                0057   int   sizeInBytesb ;
                0058   int   nbElements ;
                0059 } ADMM_ChunkInfo ;
                0060
                0061 typedef struct {
                0062   void** pp ;
                0063   void** ppb ;
                0064 } ADMM_WaitingAddress ;
                0065
                0066 ADMM_List admm_chunksByBaseCell = {NULL, NULL} ;
                0067 ADMM_List admm_chunksByObaseCell = {NULL, NULL} ;
                0068 ADMM_List admm_chunksByBasebCell = {NULL, NULL} ;
                0069 ADMM_List admm_chunksByObasebCell = {NULL, NULL} ;
                0070 ADMM_List* admm_chunksLists[] =
                0071   {&admm_chunksByBaseCell, &admm_chunksByObaseCell, &admm_chunksByBasebCell, &admm_chunksByObasebCell};
                0072
                0073 ADMM_List admm_waitingRebasesRoot = {NULL, NULL} ;
                0074 ADMM_List *admm_waitingRebases = &admm_waitingRebasesRoot ;
                0075
                0076
                0077 void ADMM_insertChunkInfo(ADMM_ChunkInfo* newChunkInfo, void* base, ADMM_AddrSort index) {
                0078   ADMM_List *toList = admm_chunksLists[index] ;
                0079   // search for the place where to insert the ADMM_ChunkInfo:
                0080   while (toList->tail && ((ADMM_ChunkInfo*)toList->tail->head)->bases[index]<base) {
                0081     toList = toList->tail ;
                0082   }
                0083   // insert at that place:
                0084   ADMM_List* newCell = (ADMM_List*)malloc(sizeof(ADMM_List)) ;
                0085   newCell->head = newChunkInfo ;
                0086   newCell->tail = toList->tail ;
                0087   toList->tail = newCell ;
                0088 }
                0089
                0090 ADMM_ChunkInfo* ADMM_searchBase(void* base, ADMM_AddrSort index) {
                0091   ADMM_List *inList = admm_chunksLists[index]->tail ;
                0092   ADMM_ChunkInfo* chunk ;
                0093   // search for the ADMM_ChunkInfo about the chunk with the given base:
                0094   while (inList) {
                0095     chunk = (ADMM_ChunkInfo*)inList->head ;
                0096     if (chunk->bases[index]==base) return chunk ;
                0097     inList = inList->tail ;
                0098   }
                0099   return NULL ;
                0100 }
                0101
                0102 ADMM_ChunkInfo* ADMM_searchAddress(void* address, ADMM_AddrSort index) {
                0103   ADMM_List *inList = admm_chunksLists[index]->tail ;
                0104   ADMM_ChunkInfo* chunk ;
                0105   // search for the ADMM_ChunkInfo that contains the address:
                0106   while (inList) {
                0107     chunk = (ADMM_ChunkInfo*)inList->head ;
                0108     if (chunk->bases[index]<=address &&
                0109         address<(chunk->bases[index]+(index<BYBASEB?chunk->sizeInBytes:chunk->sizeInBytesb)))
                0110       return chunk ;
                0111     inList = inList->tail ;
                0112   }
                0113   return NULL ;
                0114 }
                0115
                0116 void ADMM_removeChunkInfo(ADMM_ChunkInfo* chunkInfo, ADMM_AddrSort index) {
                0117   ADMM_List *toList = admm_chunksLists[index] ;
                0118   // search for the ADMM_ChunkInfo in the list:
                0119   while (toList->tail) {
                0120     if (toList->tail->head==chunkInfo) {
                0121       ADMM_List* cell = toList->tail ;
                0122       toList->tail = cell->tail ;
                0123       free(cell) ;
                0124       return ;
                0125     }
                0126     toList = toList->tail ;
                0127   }
                0128 }
                0129
                0130 void ADMM_findRanksInWaitings(void** pointer, void** pointerb, long* indexInWait, long* numberInWait) {
                0131   // Just for tracing ADMM, returns the length of the waitinglist and the rank in it of pointer/pointerb.
                0132   ADMM_List* inWaitingRebases = admm_waitingRebases->tail ;
                0133   ADMM_WaitingAddress* waitingAddress ;
                0134   *indexInWait = 0 ;
                0135   *numberInWait = 0 ;
                0136   while (inWaitingRebases) {
                0137     waitingAddress = (ADMM_WaitingAddress*)inWaitingRebases->head ;
                0138     ++(*numberInWait);
                0139     if (waitingAddress->pp==pointer && waitingAddress->ppb==pointerb) *indexInWait = *numberInWait ;
                0140     inWaitingRebases = inWaitingRebases->tail ;
                0141   }
                0142 }
                0143
                0144 void ADMM_addWaitingRebase(void** pointer, void** pointerb) {
                0145   // First, check if the same pointer(s) are maybe already waiting for a rebase,
                0146   // (for another, previous address, and rebasing this address has never been possible).
                0147   // In that case this waiting rebase can be reused as the new waiting rebase.
                0148   ADMM_List* inWaitingRebases = admm_waitingRebases->tail ;
                0149   ADMM_WaitingAddress* waitingAddress ;
                0150   int found = 0 ;
                0151 #ifdef ADMM_TIME_SEARCHING
                0152   startSearchTime = clock() ;
                0153 #endif
                0154   while (!found && inWaitingRebases) {
                0155     waitingAddress = (ADMM_WaitingAddress*)inWaitingRebases->head ;
                0156     found = (waitingAddress->pp==pointer && waitingAddress->ppb==pointerb) ;
                0157     inWaitingRebases = inWaitingRebases->tail ;
                0158   }
                0159 #ifdef ADMM_TIME_SEARCHING
                0160   endSearchTime = clock() ;
                0161   timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0162 #endif
                0163   // If these pointers were not already waiting, add them into the waiting list:
                0164   if (!found) {
                0165     ADMM_List *newCell = (ADMM_List*)malloc(sizeof(ADMM_List)) ;
                0166     newCell->tail = admm_waitingRebases->tail ;
                0167     newCell->head = (ADMM_WaitingAddress*)malloc(sizeof(ADMM_WaitingAddress)) ;
                0168 #ifdef ADMM_COUNTS
                0169     ++numberOfWaitings ;
                0170     if (peakNumberOfWaitings<numberOfWaitings) peakNumberOfWaitings = numberOfWaitings ;
                0171 #endif
                0172     ((ADMM_WaitingAddress*)newCell->head)->pp = pointer ;
                0173     ((ADMM_WaitingAddress*)newCell->head)->ppb = pointerb ;
                0174     admm_waitingRebases->tail = newCell ;
                0175   }
                0176 }
                0177
                0178 /** The given chunk provides for both the primal and its derivative.
                0179  * The waitingAddress can expect for a primal or a derivative or for both. */
                0180 int ADMM_chunkInfoShadowedSolvesWaiting(ADMM_ChunkInfo* chunk, ADMM_WaitingAddress* waitingAddress) {
                0181   int match = 0 ;
                0182   if (waitingAddress->pp && *(waitingAddress->pp))
                0183     match = (chunk->bases[BYOBASE]<=*(waitingAddress->pp)
                0184              && *(waitingAddress->pp)<(chunk->bases[BYOBASE]+chunk->sizeInBytes)) ;
                0185   else if (waitingAddress->ppb && *(waitingAddress->ppb))
                0186     match = (chunk->bases[BYOBASEB]<=*(waitingAddress->ppb)
                0187              && *(waitingAddress->ppb)<(chunk->bases[BYOBASEB]+chunk->sizeInBytesb)) ;
                0188   if (match) {
                0189     if (waitingAddress->pp && *(waitingAddress->pp))
                0190       *(waitingAddress->pp) = chunk->bases[BYBASE]+(*(waitingAddress->pp)-chunk->bases[BYOBASE]) ;
                0191     if (waitingAddress->ppb && *(waitingAddress->ppb))
                0192       *(waitingAddress->ppb) = chunk->bases[BYBASEB]+(*(waitingAddress->ppb)-chunk->bases[BYOBASEB]) ;
                0193 #ifdef ADMM_COUNTS
                0194     ++numberOfRebases ;
                0195 #endif
                0196     return 1 ;
                0197   } else
                0198     return 0 ;
                0199 }
                0200
                0201 /** The given chunk is only for the primal.
                0202  * The waitingAddress can only expect for a primal. If it expects a derivative -> error! */
                0203 int ADMM_chunkInfoSolvesWaiting(ADMM_ChunkInfo* chunk, ADMM_WaitingAddress* waitingAddress) {
                0204   int match = (waitingAddress->pp && *(waitingAddress->pp)
                0205                && chunk->bases[BYOBASE]<=*(waitingAddress->pp)
                0206                && *(waitingAddress->pp)<(chunk->bases[BYOBASE]+chunk->sizeInBytes)) ;
                0207   if (match) {
                0208     *(waitingAddress->pp) = chunk->bases[BYBASE]+(*(waitingAddress->pp)-chunk->bases[BYOBASE]) ;
                0209 #ifdef ADMM_COUNTS
                0210     ++numberOfRebases ;
                0211 #endif
                0212     return 1 ;
                0213   } else
                0214     return 0 ;
                0215 }
                0216
                0217 /** Remove waiting addresses and addressesb that will never be solved
                0218  * because they are contained in pointers that are beeing freed. */
                0219 void ADMM_cleanDeadWaitingsShadowed(void *base, int size, void *baseb, int sizeb) {
                0220   ADMM_List* inWaitingRebases = admm_waitingRebases ;
                0221   ADMM_List* waitingCell ;
                0222 #ifdef ADMM_TIME_SEARCHING
                0223   startSearchTime = clock() ;
                0224 #endif
                0225   while (inWaitingRebases->tail) {
                0226     waitingCell = inWaitingRebases->tail ;
                0227     if (
                0228         (base <= (void*)((ADMM_WaitingAddress*)waitingCell->head)->pp &&
                0229          (void*)((ADMM_WaitingAddress*)waitingCell->head)->pp < base+size)
                0230         ||
                0231         (baseb && ((ADMM_WaitingAddress*)waitingCell->head)->ppb &&
                0232          baseb <= (void*)((ADMM_WaitingAddress*)waitingCell->head)->ppb &&
                0233          (void*)((ADMM_WaitingAddress*)waitingCell->head)->ppb < baseb+sizeb)
                0234         ) {
                0235 #ifdef ADMM_TRACE
                0236       printf(" clean waiting [%li]->%li Shadow:[%li]->%li\n", ((ADMM_WaitingAddress*)waitingCell->head)->pp, (((ADMM_WaitingAddress*)waitingCell->head)->pp?*(((ADMM_WaitingAddress*)waitingCell->head)->pp):NULL), ((ADMM_WaitingAddress*)waitingCell->head)->ppb, (((ADMM_WaitingAddress*)waitingCell->head)->ppb?*(((ADMM_WaitingAddress*)waitingCell->head)->ppb):NULL)) ;
                0237       fflush(stdout);
                0238 #endif
                0239       inWaitingRebases->tail = inWaitingRebases->tail->tail ;
                0240       free(waitingCell->head) ;
                0241       free(waitingCell) ;
                0242 #ifdef ADMM_COUNTS
                0243       --numberOfWaitings ;
                0244 #endif
                0245     } else
                0246       inWaitingRebases = inWaitingRebases->tail ;
                0247   }
                0248 #ifdef ADMM_TIME_SEARCHING
                0249   endSearchTime = clock() ;
                0250   timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0251 #endif
                0252 }
                0253
                0254 void ADMM_registerShadowed(void *base, void *obase, int sizeInBytes, void *baseb, void **alreadyRebasedb, void *obaseb, int sizeInBytesb, int nbElements
                0255 #ifdef ADMM_LABELS
                0256 , char *label) {
                0257 #else
                0258 ) {char *label = "" ;
                0259 #endif
                0260 #ifdef ADMM_TIME
                0261   startADMMTime = clock() ;
                0262 #endif
                0263   int rebasePhase = (obaseb!=0) ;
                0264   ADMM_ChunkInfo* newChunkInfo = (ADMM_ChunkInfo*)malloc(sizeof(ADMM_ChunkInfo)) ;
                0265 #ifdef ADMM_COUNTS
                0266   ++numberOfChunks ;
                0267   if (numberOfChunks>peakNumberOfChunks) peakNumberOfChunks = numberOfChunks ;
                0268   ++numberOfRegisterings ;
                0269 #endif
                0270 #ifdef ADMM_TRACE
                0271   if (rebasePhase)
                0272     printf("ADMM_register (old:%li=>)%li+%i    Shadow: (old:%li=>)%li+%i \"%s\"\n", obase, base, sizeInBytes, obaseb, baseb, sizeInBytesb, label);
                0273   else
                0274     printf("ADMM_register %li+%i    Shadow: %li+%i \"%s\"\n", base, sizeInBytes, baseb, sizeInBytesb, label);
                0275   fflush(stdout);
                0276 #endif
                0277   if (!rebasePhase) {obase = base; obaseb = baseb;}
                0278   newChunkInfo->bases[0] = base ;
                0279   newChunkInfo->bases[1] = obase ;
                0280   newChunkInfo->bases[2] = baseb ;
                0281   newChunkInfo->bases[3] = obaseb ;
                0282   newChunkInfo->sizeInBytes = sizeInBytes ;
                0283   newChunkInfo->sizeInBytesb = sizeInBytesb ;
                0284   newChunkInfo->nbElements = nbElements ;
                0285 #ifdef ADMM_TIME_SEARCHING
                0286   startSearchTime = clock() ;
                0287 #endif
                0288   ADMM_insertChunkInfo(newChunkInfo, base, BYBASE) ;
                0289   ADMM_insertChunkInfo(newChunkInfo, obase, BYOBASE) ;
                0290   ADMM_insertChunkInfo(newChunkInfo, baseb, BYBASEB) ;
                0291   ADMM_insertChunkInfo(newChunkInfo, obaseb, BYOBASEB) ;
                0292   if (rebasePhase) {
                0293     /* Now solve waiting pointers and pointerbs with newChunkInfo: */
                0294     ADMM_List* inWaitingRebases = admm_waitingRebases ;
                0295     ADMM_List* waitingCell ;
                0296     while (inWaitingRebases->tail) {
                0297       waitingCell = inWaitingRebases->tail ;
                0298 #ifdef ADMM_TRACE
                0299       printf("   ...retry rebase [%li]->%li Shadow:[%li]->%li ?", ((ADMM_WaitingAddress*)waitingCell->head)->pp, (((ADMM_WaitingAddress*)waitingCell->head)->pp?*(((ADMM_WaitingAddress*)waitingCell->head)->pp):NULL), ((ADMM_WaitingAddress*)waitingCell->head)->ppb, (((ADMM_WaitingAddress*)waitingCell->head)->ppb?*(((ADMM_WaitingAddress*)waitingCell->head)->ppb):NULL)) ;
                0300       fflush(stdout);
                0301 #endif
                0302       if (alreadyRebasedb==((ADMM_WaitingAddress*)waitingCell->head)->ppb) {
                0303 #ifdef ADMM_TRACE
                0304         printf(" now done => [%li]->%li Shadow:[%li]->%li !\n", ((ADMM_WaitingAddress*)waitingCell->head)->pp, (((ADMM_WaitingAddress*)waitingCell->head)->pp?*(((ADMM_WaitingAddress*)waitingCell->head)->pp):NULL), ((ADMM_WaitingAddress*)waitingCell->head)->ppb, (((ADMM_WaitingAddress*)waitingCell->head)->ppb?*(((ADMM_WaitingAddress*)waitingCell->head)->ppb):NULL)) ;
                0305         fflush(stdout);
                0306 #endif
                0307         inWaitingRebases->tail = inWaitingRebases->tail->tail ;
                0308         free(waitingCell->head) ;
                0309         free(waitingCell) ;
                0310       } else if (ADMM_chunkInfoShadowedSolvesWaiting(newChunkInfo, (ADMM_WaitingAddress*)waitingCell->head)) {
                0311 #ifdef ADMM_TRACE
                0312         printf(" yes => [%li]->%li Shadow:[%li]->%li !\n", ((ADMM_WaitingAddress*)waitingCell->head)->pp, (((ADMM_WaitingAddress*)waitingCell->head)->pp?*(((ADMM_WaitingAddress*)waitingCell->head)->pp):NULL), ((ADMM_WaitingAddress*)waitingCell->head)->ppb, (((ADMM_WaitingAddress*)waitingCell->head)->ppb?*(((ADMM_WaitingAddress*)waitingCell->head)->ppb):NULL)) ;
                0313         fflush(stdout);
                0314 #endif
                0315         inWaitingRebases->tail = inWaitingRebases->tail->tail ;
                0316         free(waitingCell->head) ;
                0317         free(waitingCell) ;
                0318 #ifdef ADMM_COUNTS
                0319         --numberOfWaitings ;
                0320 #endif
                0321       } else {
                0322 #ifdef ADMM_TRACE
                0323         printf(" no, try again later!\n") ;
                0324         fflush(stdout);
                0325 #endif
                0326         inWaitingRebases = inWaitingRebases->tail ;
                0327       }
                0328     }
                0329   }
                0330 #ifdef ADMM_TIME_SEARCHING
                0331   endSearchTime = clock() ;
                0332   timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0333 #endif
                0334 #ifdef ADMM_TIME
                0335   endADMMTime = clock() ;
                0336   timeSpentInADMM += ((double)(endADMMTime-startADMMTime))/((double)CLOCKS_PER_SEC) ;
                0337 #endif
                0338 }
                0339
                0340 void ADMM_register(void *base, void **alreadyRebased, void *obase, int sizeInBytes, int nbElements
                0341 #ifdef ADMM_LABELS
                0342 , char *label) {
                0343 #else
                0344 ) {char *label = "" ;
                0345 #endif
                0346 #ifdef ADMM_TIME
                0347   startADMMTime = clock() ;
                0348 #endif
                0349   int rebasePhase = (obase!=0) ;
                0350   ADMM_ChunkInfo* newChunkInfo = (ADMM_ChunkInfo*)malloc(sizeof(ADMM_ChunkInfo)) ;
                0351 #ifdef ADMM_COUNTS
                0352   ++numberOfChunks ;
                0353   if (numberOfChunks>peakNumberOfChunks) peakNumberOfChunks = numberOfChunks ;
                0354   ++numberOfRegisterings ;
                0355 #endif
                0356 #ifdef ADMM_TRACE
                0357   if (rebasePhase)
                0358     printf("ADMM_register (old:%li=>)%li+%i \"%s\"\n", obase, base, sizeInBytes, label);
                0359   else
                0360     printf("ADMM_register %li+%i \"%s\"\n", base, sizeInBytes, label);
                0361   fflush(stdout);
                0362 #endif
                0363   if (!rebasePhase) obase = base ;
                0364   newChunkInfo->bases[0] = base ;
                0365   newChunkInfo->bases[1] = obase ;
                0366   newChunkInfo->bases[2] = NULL ;
                0367   newChunkInfo->bases[3] = NULL ;
                0368   newChunkInfo->sizeInBytes = sizeInBytes ;
                0369   newChunkInfo->sizeInBytesb = 0 ;
                0370   newChunkInfo->nbElements = nbElements ;
                0371 #ifdef ADMM_TIME_SEARCHING
                0372   startSearchTime = clock() ;
                0373 #endif
                0374   ADMM_insertChunkInfo(newChunkInfo, base, BYBASE) ;
                0375   ADMM_insertChunkInfo(newChunkInfo, obase, BYOBASE) ;
                0376   if (rebasePhase) {
                0377     /* Now solve waiting pointers with newChunkInfo:
                0378      * NOTE: we are in the no-shadow Register case, which means that this
                0379      * memory chunk doesn't need a derivative chunk, and therefore we assume
                0380      * that there cannot be a shadowed waiting address waiting for this chunk. */
                0381     ADMM_List* inWaitingRebases = admm_waitingRebases ;
                0382     ADMM_List* waitingCell ;
                0383     while (inWaitingRebases->tail) {
                0384       waitingCell = inWaitingRebases->tail ;
                0385 #ifdef ADMM_TRACE
                0386       printf("   ...retry rebase [%li]->%li ?", ((ADMM_WaitingAddress*)waitingCell->head)->pp, (((ADMM_WaitingAddress*)waitingCell->head)->pp?*(((ADMM_WaitingAddress*)waitingCell->head)->pp):NULL)) ;
                0387       fflush(stdout);
                0388 #endif
                0389       if (alreadyRebased==((ADMM_WaitingAddress*)waitingCell->head)->pp) {
                0390 #ifdef ADMM_TRACE
                0391         printf(" now done => [%li]->%li !\n", ((ADMM_WaitingAddress*)waitingCell->head)->pp, (((ADMM_WaitingAddress*)waitingCell->head)->pp?*(((ADMM_WaitingAddress*)waitingCell->head)->pp):NULL)) ;
                0392         fflush(stdout);
                0393 #endif
                0394         inWaitingRebases->tail = inWaitingRebases->tail->tail ;
                0395         free(waitingCell->head) ;
                0396         free(waitingCell) ;
                0397       } else if (ADMM_chunkInfoSolvesWaiting(newChunkInfo, (ADMM_WaitingAddress*)waitingCell->head)) {
                0398 #ifdef ADMM_TRACE
                0399         printf(" yes => [%li]->%li !\n", ((ADMM_WaitingAddress*)waitingCell->head)->pp, (((ADMM_WaitingAddress*)waitingCell->head)->pp?*(((ADMM_WaitingAddress*)waitingCell->head)->pp):NULL)) ;
                0400         fflush(stdout);
                0401 #endif
                0402         inWaitingRebases->tail = inWaitingRebases->tail->tail ;
                0403         free(waitingCell->head) ;
                0404         free(waitingCell) ;
                0405 #ifdef ADMM_COUNTS
                0406         --numberOfWaitings ;
                0407 #endif
                0408       } else {
                0409 #ifdef ADMM_TRACE
                0410         printf(" no, try again later!\n") ;
                0411         fflush(stdout);
                0412 #endif
                0413         inWaitingRebases = inWaitingRebases->tail ;
                0414       }
                0415     }
                0416   }
                0417 #ifdef ADMM_TIME_SEARCHING
                0418   endSearchTime = clock() ;
                0419   timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0420 #endif
                0421 #ifdef ADMM_TIME
                0422   endADMMTime = clock() ;
                0423   timeSpentInADMM += ((double)(endADMMTime-startADMMTime))/((double)CLOCKS_PER_SEC) ;
                0424 #endif
                0425 }
                0426
                0427 void ADMM_unregisterShadowed(void *base, void *baseb, int *nbElements
                0428 #ifdef ADMM_LABELS
                0429 , char *label) {
                0430 #else
                0431 ) {char *label = "" ;
                0432 #endif
                0433 #ifdef ADMM_TIME
                0434   startADMMTime = clock() ;
                0435 #endif
                0436 #ifdef ADMM_TRACE
                0437   printf("ADMM_unregister %li   Shadow: %li \"%s\"\n", base, baseb, label);
                0438   fflush(stdout);
                0439 #endif
                0440   ADMM_ChunkInfo* foundChunkInfo = NULL ;
                0441 #ifdef ADMM_TIME_SEARCHING
                0442   startSearchTime = clock() ;
                0443 #endif
                0444   if (baseb)
                0445     foundChunkInfo = ADMM_searchBase(baseb, BYBASEB) ;
                0446   if (!foundChunkInfo)
                0447     foundChunkInfo = ADMM_searchBase(base, BYBASE) ;
                0448 #ifdef ADMM_TIME_SEARCHING
                0449   endSearchTime = clock() ;
                0450   timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0451 #endif
                0452   if (foundChunkInfo) {
                0453     *nbElements = foundChunkInfo->nbElements ;
                0454 #ifdef ADMM_TIME_SEARCHING
                0455     startSearchTime = clock() ;
                0456 #endif
                0457     ADMM_removeChunkInfo(foundChunkInfo, BYBASE) ;
                0458     ADMM_removeChunkInfo(foundChunkInfo, BYOBASE) ;
                0459     ADMM_removeChunkInfo(foundChunkInfo, BYBASEB) ;
                0460     ADMM_removeChunkInfo(foundChunkInfo, BYOBASEB) ;
                0461 #ifdef ADMM_TIME_SEARCHING
                0462     endSearchTime = clock() ;
                0463     timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0464 #endif
                0465     ADMM_cleanDeadWaitingsShadowed(base, foundChunkInfo->sizeInBytes, baseb, foundChunkInfo->sizeInBytesb) ;
                0466     free(foundChunkInfo) ;
                0467 #ifdef ADMM_COUNTS
                0468     ++numberOfUnregisterings ;
                0469     --numberOfChunks ;
                0470 #endif
                0471   }
                0472 #ifdef ADMM_TIME
                0473   endADMMTime = clock() ;
                0474   timeSpentInADMM += ((double)(endADMMTime-startADMMTime))/((double)CLOCKS_PER_SEC) ;
                0475 #endif
                0476 }
                0477
                0478 void ADMM_unregister(void *base, int *nbElements
                0479 #ifdef ADMM_LABELS
                0480 , char *label) {
                0481 #else
                0482 ) {char *label = "" ;
                0483 #endif
                0484 #ifdef ADMM_TIME
                0485   startADMMTime = clock() ;
                0486 #endif
                0487 #ifdef ADMM_TRACE
                0488   printf("ADMM_unregister %li \"%s\"\n", base, label);
                0489   fflush(stdout);
                0490 #endif
                0491 #ifdef ADMM_TIME_SEARCHING
                0492   startSearchTime = clock() ;
                0493 #endif
                0494   ADMM_ChunkInfo* foundChunkInfo = ADMM_searchBase(base, BYBASE) ;
                0495 #ifdef ADMM_TIME_SEARCHING
                0496   endSearchTime = clock() ;
                0497   timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0498 #endif
                0499   if (foundChunkInfo) {
                0500     *nbElements = foundChunkInfo->nbElements ;
                0501 #ifdef ADMM_TIME_SEARCHING
                0502     startSearchTime = clock() ;
                0503 #endif
                0504     ADMM_removeChunkInfo(foundChunkInfo, BYBASE) ;
                0505     ADMM_removeChunkInfo(foundChunkInfo, BYOBASE) ;
                0506 #ifdef ADMM_TIME_SEARCHING
                0507     endSearchTime = clock() ;
                0508     timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0509 #endif
                0510     ADMM_cleanDeadWaitingsShadowed(base, foundChunkInfo->sizeInBytes, NULL, 0) ;
                0511     free(foundChunkInfo) ;
                0512 #ifdef ADMM_COUNTS
                0513     ++numberOfUnregisterings ;
                0514     --numberOfChunks ;
                0515 #endif
                0516   }
                0517 #ifdef ADMM_TIME
                0518   endADMMTime = clock() ;
                0519   timeSpentInADMM += ((double)(endADMMTime-startADMMTime))/((double)CLOCKS_PER_SEC) ;
                0520 #endif
                0521 }
                0522
                0523 void ADMM_rebaseShadowed(void** pointer, void** pointerb
                0524 #ifdef ADMM_LABELS
                0525 , char *label) {
                0526 #else
                0527 ) {char *label = "" ;
                0528 #endif
                0529 #ifdef ADMM_TIME
                0530   startADMMTime = clock() ;
                0531 #endif
                0532 #ifdef ADMM_TRACE
                0533   printf("   ADMM_rebase [%li]->%li Shadow:[%li]->%li \"%s\" ?", pointer, (pointer?*pointer:NULL), pointerb, (pointerb?*pointerb:NULL), label) ;
                0534   fflush(stdout);
                0535 #endif
                0536   ADMM_ChunkInfo* foundChunkInfo = NULL ;
                0537 #ifdef ADMM_TIME_SEARCHING
                0538   startSearchTime = clock() ;
                0539 #endif
                0540   if (*pointerb)
                0541     foundChunkInfo = ADMM_searchAddress(*pointerb, BYOBASEB) ;
                0542   if (!foundChunkInfo && pointer && *pointer)
                0543     foundChunkInfo = ADMM_searchAddress(*pointer, BYOBASE) ;
                0544 #ifdef ADMM_TIME_SEARCHING
                0545     endSearchTime = clock() ;
                0546     timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0547 #endif
                0548   if (foundChunkInfo) {
                0549     if (pointer && *pointer)
                0550       *pointer = foundChunkInfo->bases[BYBASE]+(*pointer-foundChunkInfo->bases[BYOBASE]) ;
                0551     if (*pointerb)
                0552       *pointerb = foundChunkInfo->bases[BYBASEB]+(*pointerb-foundChunkInfo->bases[BYOBASEB]) ;
                0553 #ifdef ADMM_TRACE
                0554     printf(" yes => [%li]->%li Shadow:[%li]->%li !\n", pointer, (pointer?*pointer:NULL), pointerb, (pointerb?*pointerb:NULL)) ;
                0555     printf("  from (old:%li=>)%li+%i    Shadow: (old:%li=>)%li+%i\n", foundChunkInfo->bases[BYOBASE], foundChunkInfo->bases[BYBASE], foundChunkInfo->sizeInBytes, foundChunkInfo->bases[BYOBASEB], foundChunkInfo->bases[BYBASEB], foundChunkInfo->sizeInBytesb);
                0556     fflush(stdout);
                0557 #endif
                0558   } else if ((pointer && *pointer) || *pointerb) {
                0559     ADMM_addWaitingRebase(pointer, pointerb) ;
                0560 #ifdef ADMM_TRACE
                0561     long indexInWait, numberInWait ;
                0562     ADMM_findRanksInWaitings(pointer, pointerb, &indexInWait, &numberInWait) ;
                0563     printf(" no  => add to waiting list [%li/%li]\n",indexInWait,numberInWait) ;
                0564     fflush(stdout);
                0565 #endif
                0566   } else {
                0567 #ifdef ADMM_TRACE
                0568     printf(".\n") ;
                0569     fflush(stdout);
                0570 #endif
                0571   }
                0572 #ifdef ADMM_COUNTS
                0573   ++numberOfRebases ;
                0574 #endif
                0575 #ifdef ADMM_TIME
                0576   endADMMTime = clock() ;
                0577   timeSpentInADMM += ((double)(endADMMTime-startADMMTime))/((double)CLOCKS_PER_SEC) ;
                0578 #endif
                0579 }
                0580
                0581
                0582 void ADMM_rebase(void** pointer
                0583 #ifdef ADMM_LABELS
                0584 , char *label) {
                0585 #else
                0586 ) {char *label = "" ;
                0587 #endif
                0588 #ifdef ADMM_TIME
                0589   startADMMTime = clock() ;
                0590 #endif
                0591 #ifdef ADMM_TRACE
                0592   printf("   ADMM_rebase [%li]->%li \"%s\" ?", pointer, (pointer?*pointer:NULL), label) ;
                0593   fflush(stdout);
                0594 #endif
                0595   ADMM_ChunkInfo* foundChunkInfo = NULL ;
                0596   if (*pointer) {
                0597 #ifdef ADMM_TIME_SEARCHING
                0598     startSearchTime = clock() ;
                0599 #endif
                0600     foundChunkInfo = ADMM_searchAddress(*pointer, BYOBASE) ;
                0601 #ifdef ADMM_TIME_SEARCHING
                0602     endSearchTime = clock() ;
                0603     timeSpentSearching += ((double)(endSearchTime-startSearchTime))/((double)CLOCKS_PER_SEC) ;
                0604 #endif
                0605     if (foundChunkInfo) {
                0606       *pointer = foundChunkInfo->bases[BYBASE]+(*pointer-foundChunkInfo->bases[BYOBASE]) ;
                0607 #ifdef ADMM_TRACE
                0608       printf(" yes => [%li]->%li !\n", pointer, (pointer?*pointer:NULL)) ;
                0609       printf("  from (old:%li=>)%li+%i    Shadow: (old:%li=>)%li+%i\n", foundChunkInfo->bases[BYOBASE], foundChunkInfo->bases[BYBASE], foundChunkInfo->sizeInBytes, foundChunkInfo->bases[BYOBASEB], foundChunkInfo->bases[BYBASEB], foundChunkInfo->sizeInBytesb);
                0610       fflush(stdout);
                0611 #endif
                0612     } else {
                0613       ADMM_addWaitingRebase(pointer, NULL) ;
                0614 #ifdef ADMM_TRACE
                0615       long indexInWait, numberInWait ;
                0616       ADMM_findRanksInWaitings(pointer, NULL, &indexInWait, &numberInWait) ;
                0617       printf(" no  => add to waiting list [%li/%li]\n",indexInWait,numberInWait) ;
                0618       fflush(stdout);
                0619 #endif
                0620     }
                0621   } else {
                0622 #ifdef ADMM_TRACE
                0623     printf(".\n") ;
                0624     fflush(stdout);
                0625 #endif
                0626   }
                0627 #ifdef ADMM_COUNTS
                0628   ++numberOfRebases ;
                0629 #endif
                0630 #ifdef ADMM_TIME
                0631   endADMMTime = clock() ;
                0632   timeSpentInADMM += ((double)(endADMMTime-startADMMTime))/((double)CLOCKS_PER_SEC) ;
                0633 #endif
                0634 }
                0635
                0636 #ifdef ADMM_COUNTS
                0637 void ADMM_showChunks() {
                0638   ADMM_List* inChunksByBaseCell = admm_chunksByBaseCell.tail ;
                0639   ADMM_ChunkInfo* chunkInfo ;
                0640   printf("CHUNKS LIST:\n") ;
                0641   while (inChunksByBaseCell) {
                0642     chunkInfo = ((ADMM_ChunkInfo*)inChunksByBaseCell->head) ;
                0643     printf("  (old:%li=>)%li+%i    Shadow: (old:%li=>)%li+%i (%i elements)\n",
                0644            chunkInfo->bases[BYOBASE], chunkInfo->bases[BYBASE], chunkInfo->sizeInBytes,
                0645            chunkInfo->bases[BYOBASEB], chunkInfo->bases[BYBASEB], chunkInfo->sizeInBytesb,
                0646            chunkInfo->nbElements);
                0647     inChunksByBaseCell = inChunksByBaseCell->tail ;
                0648   }
                0649   fflush(stdout);
                0650 }
                0651 #endif
                0652
                0653 #ifdef ADMM_COUNTS
                0654 void ADMM_showWaitings() {
                0655   ADMM_List* inWaitingRebases = admm_waitingRebases->tail ;
                0656   ADMM_WaitingAddress* waitingAddress ;
                0657   printf("WAITING LIST:\n") ;
                0658   while (inWaitingRebases) {
                0659     waitingAddress = (ADMM_WaitingAddress*)inWaitingRebases->head ;
                0660     printf(" [%li]->%li Shadow:[%li]->%li   %x %x \n",
                0661            waitingAddress->pp, (waitingAddress->pp?*(waitingAddress->pp):NULL),
                0662            waitingAddress->ppb, (waitingAddress->ppb?*(waitingAddress->ppb):NULL),
                0663            waitingAddress->pp, waitingAddress->ppb);
                0664     inWaitingRebases = inWaitingRebases->tail ;
                0665   }
                0666   printf("\n");
                0667   fflush(stdout);
                0668 }
                0669 #endif
                0670
                0671 void ADMM_statistics() {
                0672 #ifdef ADMM_TIME
                0673   printf("Time spent in ADMM:%lf\n", timeSpentInADMM) ;
                0674 #endif
                0675 #ifdef ADMM_TIME_SEARCHING
                0676   printf("Time spent searching:%lf\n", timeSpentSearching) ;
                0677 #endif
                0678 #ifdef ADMM_COUNTS
                0679   printf("Registerings:%i, Unregisterings:%i, numberOfRebases:%i\n",
                0680          numberOfRegisterings, numberOfUnregisterings, numberOfRebases) ;
                0681   printf("chunks:%i[peak:%i] waiting:%i[peak:%i]\n",
                0682          numberOfChunks, peakNumberOfChunks, numberOfWaitings, peakNumberOfWaitings);
                0683   ADMM_showChunks() ;
                0684   ADMM_showWaitings() ;
                0685 #endif
                0686   fflush(stdout);
                0687 }