bugFreeciv - Bugs: bug #21988, Genhash collision handling very...

 
 
Show feedback again

bug #21988: Genhash collision handling very inefficient

Submitted by:  Marko Lindqvist <cazfi>
Submitted on:  Mon 28 Apr 2014 10:40:24 PM UTC  
 
Category: generalSeverity: 3 - Normal
Priority: 5 - NormalStatus: Fixed
Assigned to: pepeto <pepeto>Open/Closed: Closed
Release: Operating System: None
Planned Release: 2.6.0

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Tue 20 May 2014 09:29:15 PM UTC, SVN revision 24910:

Rewrite hash table module to use open hashing. Collision
resolution is now done by separate chaining with linked lists.

Reported by Marko Lindqvist (cazfi@gna)

See bug #21988

(Browse SVN revision 24910)

pepeto <pepeto>
Project MemberIn charge of this item.
Wed 14 May 2014 09:47:24 AM UTC, comment #7:

I have investigated the game produced by your script.

Valgrind output isn't different.

Savegames differs, notably the player maps.

The only difference between without and with the patch applied is that the entries of the hash table are not listed in the same order. It is due to how collisions are handled, and how resizing is done. The order of the hash table doesn't matter, but it has big consequences on the game.

First of all, start positions aren't attributed to the same players (see Player1 and Atawallpa). I think this is the biggest cause of the difference between the autogames.

I attach the script used for comment #5, where no different was notable (I guess that start positions were luckily listed in the same order).

(file #20737)

pepeto <pepeto>
Project MemberIn charge of this item.
Tue 13 May 2014 09:25:10 PM UTC, comment #6:

Attached is the autogame I used earlier and which does differ (it's my standard regression testing autogame)

(file #20733)

Marko Lindqvist <cazfi>
Project Administrator
Tue 13 May 2014 09:13:27 PM UTC, comment #5:

> I used same mapseed, gameseed and same options, but I didn't
> get the same number of function call. I don't know why (maybe a
> memory error in the patch).


Actually, I was trying to set too big seeds, so they weren't taken in account...

There is the stats without the patch:

and the same stats with the patch applied:

It looks all right.

pepeto <pepeto>
Project MemberIn charge of this item.
Thu 08 May 2014 09:56:40 PM UTC, comment #4:

Autogames differ, and I don't see how that could be right (even if two items have same hash and thus there's collision, correct bucket should be found in the end)

Marko Lindqvist <cazfi>
Project Administrator
Tue 06 May 2014 09:34:59 PM UTC, comment #3:

> Now waiting to performance comments...


At least the source reads like what I had in mind. I'll setup some test runs by the end of the week.

Marko Lindqvist <cazfi>
Project Administrator
Tue 06 May 2014 04:06:33 PM UTC, comment #2:

Second version of the patch: fix that the number of entries is correct and refactor genhash_resize_table().

I have tested all functions. It looks to work as expected. Now waiting to performance comments...

(file #20663)

pepeto <pepeto>
Project MemberIn charge of this item.
Mon 05 May 2014 09:07:48 PM UTC, comment #1:

The attached patch implements open hashing with chained list resolution.

I tried to use gprof (I doubt I did all right for my first attempt). Here the stats I of the main genhash functions I get before applying the patch:

Here with the patch:

I used same mapseed, gameseed and same options, but I didn't get the same number of function call. I don't know why (maybe a memory error in the patch).

Waiting for comments or advices to improve the patch.

(file #20644)

pepeto <pepeto>
Project MemberIn charge of this item.
Mon 28 Apr 2014 10:40:24 PM UTC, original submission:

This is followup to bug #21972. Ganhash must be rewritten in a way that avoids chain-reactions when one collision sends entry to another bucket causing another collision there, and especially traversing half the table looking for the entry, just in case collisions have thrown it far away from its own bucket, when it is in fact deleted. Latter can often happen when lookup is used with the exact goal of checking if entry still exist (is unit still alive or city not destroyed).

Marko Lindqvist <cazfi>
Project Administrator

 

(Note: upload size limit is set to 1024 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #20737:  TEST.serv added by pepeto (215B - application/octet-stream)
file #20733:  regression.serv added by cazfi (287B - application/octet-stream)
file #20663:  genhash2.diff added by pepeto (23kB - text/x-diff)
file #20644:  genhash.diff added by pepeto (21kB - text/x-diff)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by pepeto (Updated the item)
  • -unavailable- added by pepeto
  • -unavailable- added by cazfi (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 12 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 20 May 2014 09:29:30 PM UTCpepetoStatusReady For Test=>Fixed
      Open/ClosedOpen=>Closed
    Sun 18 May 2014 09:24:20 PM UTCpepetoAssigned toNone=>pepeto
    Wed 14 May 2014 09:47:24 AM UTCpepetoAttached File-=>Added TEST.serv, #20737
    Tue 13 May 2014 09:25:10 PM UTCcazfiAttached File-=>Added regression.serv, #20733
    Tue 06 May 2014 09:34:59 PM UTCcazfiCategoryNone=>general
      Planned Release=>2.6.0
    Tue 06 May 2014 04:06:33 PM UTCpepetoAttached File-=>Added genhash2.diff, #20663
      StatusIn Progress=>Ready For Test
    Mon 05 May 2014 09:07:48 PM UTCpepetoAttached File-=>Added genhash.diff, #20644
      StatusNone=>In Progress
    Tue 29 Apr 2014 07:44:36 AM UTCpepetoCarbon-Copy-=>Added -unavailable-
    Show feedback again

    Back to the top


    Powered by Savane 3.1-cleanup