[Mono-bugs] [Bug 542478] New: Hashing pthread-ids over GC_threads-array sub optimal

[bugzilla_noreply at novell.com]

http://bugzilla.novell.com/show_bug.cgi?id=542478


           Summary: Hashing pthread-ids over GC_threads-array sub optimal
    Classification: Mono
           Product: Mono: Runtime
           Version: 2.4.x
          Platform: Macintosh
        OS/Version: Mac OS X 10.6
            Status: NEW
          Severity: Minor
          Priority: P5 - None
         Component: GC
        AssignedTo: lupus at novell.com
        ReportedBy: mahegdels at telenet.be
         QAContact: mono-bugs at lists.ximian.com
          Found By: ---


User-Agent:       Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_1; en-us)
AppleWebKit/531.9 (KHTML, like Gecko) Version/4.0.3 Safari/531.9

The GC_Threads-array is probably not optimally filled.

The index in the array of a certain pthread is calculated as follows:
   int hv = ((word)id) % THREAD_TABLE_SZ;
THREAD_TABLE_SZ is defined as 128.

However the pthread_id (on snow leopard at least - not tested on other
platforms) are multiples of 128 which results in a situation that all threads
are stored only in the linked list behind element 0 in the GC_threads array.
This make this linked list quite long to scan and hence it is probably more
efficient to  use another algorithm to hash over the table.

The following small program creates 100 threads, prints the pthread_id and the
calculated entry in the GC_threads array:

#include <pthread.h>
#define THREAD_TABLE_SZ 128
void *start_routine(void *data)
{
   return;
}

int main()
{
   int i;

   for (i=0; i<100; i++) {
       pthread_t id;
       int ret = pthread_create(&id, NULL, start_routine, NULL);
       printf("%3i %p %li\n", i, id, (long)id%THREAD_TABLE_SZ);
   }
}

The output is:
  0 0x1000a2000 0
  1 0x100281000 0
  2 0x100304000 0
  3 0x100387000 0
  4 0x10040a000 0
  5 0x10048d000 0
  6 0x100510000 0
  7 0x100593000 0
  8 0x100616000 0
  9 0x100699000 0
 10 0x10071c000 0
 11 0x10079f000 0
 12 0x101081000 0
 13 0x101104000 0
 14 0x101187000 0
 15 0x10120a000 0
 16 0x10128d000 0
 17 0x101310000 0
 18 0x101393000 0
 19 0x101416000 0
 20 0x101499000 0
 21 0x10151c000 0
 22 0x10159f000 0
 23 0x101622000 0
 24 0x1016a5000 0
 25 0x101728000 0
 26 0x1017ab000 0
 27 0x10182e000 0
 28 0x1018b1000 0
 29 0x101934000 0
 30 0x1019b7000 0
 31 0x101a3a000 0
 32 0x101abd000 0
 33 0x101c81000 0
 34 0x101d04000 0
 35 0x101d87000 0
 36 0x101e0a000 0
 37 0x101e8d000 0
 38 0x101f10000 0
 39 0x101f93000 0
 40 0x102016000 0
 41 0x102099000 0
 42 0x10211c000 0
 43 0x10219f000 0
 44 0x102222000 0
 45 0x1022a5000 0
 46 0x102328000 0
 47 0x1023ab000 0
 48 0x10242e000 0
 49 0x1024b1000 0
 50 0x102534000 0
 51 0x1025b7000 0
 52 0x10263a000 0
 53 0x1026bd000 0
 54 0x102740000 0
 55 0x1027c3000 0
 56 0x102846000 0
 57 0x1028c9000 0
 58 0x10294c000 0
 59 0x1029cf000 0
 60 0x102a52000 0
 61 0x102ad5000 0
 62 0x102b58000 0
 63 0x102bdb000 0
 64 0x102c5e000 0
 65 0x102ce1000 0
 66 0x102d64000 0
 67 0x102de7000 0
 68 0x102e6a000 0
 69 0x102eed000 0
 70 0x102f70000 0
 71 0x102ff3000 0
 72 0x103076000 0
 73 0x1030f9000 0
 74 0x10317c000 0
 75 0x1031ff000 0
 76 0x103282000 0
 77 0x103305000 0
 78 0x103388000 0
 79 0x10340b000 0
 80 0x10348e000 0
 81 0x103511000 0
 82 0x103594000 0
 83 0x103617000 0
 84 0x10369a000 0
 85 0x10371d000 0
 86 0x1037a0000 0
 87 0x103823000 0
 88 0x1038a6000 0
 89 0x103929000 0
 90 0x1039ac000 0
 91 0x103a2f000 0
 92 0x103ab2000 0
 93 0x103b35000 0
 94 0x103bb8000 0
 95 0x103c3b000 0
 96 0x103cbe000 0
 97 0x103d41000 0
 98 0x103dc4000 0
 99 0x103e47000 0


The third element defines the entry in the GC_threads table. All are 0.
This proves that all threads are stashed in the linked list behind the first
GC_threads element.


Reproducible: Always

Steps to Reproduce:
1.
2.
3.
Actual Results:  
All threads are stashed behind the first element in the GC_threads array

Expected Results:  
All threads are stashed behind different elements in the GC_threads array to
improve performance as linked lists are smaller

-- 
Configure bugmail: http://bugzilla.novell.com/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.