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 Apr 28 22:40:24 2014  
 
Category: generalSeverity: 3 - Normal
Priority: 5 - NormalStatus: Fixed
Assigned to: pepeto <pepeto>Open/Closed: Closed
Release: Operating System: None
Planned Release: 2.6.0Contains string changes: None

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)

Thu Jan 1 09:40:57 2015, comment #9:

This is being backported to S2_5 as part of patch #5632

Marko Lindqvist <cazfi>
Project Administrator
Tue May 20 21:29:15 2014, 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 May 14 09:47:24 2014, 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 May 13 21:25:10 2014, 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 May 13 21:13:27 2014, 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 May 8 21:56:40 2014, 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 May 6 21:34:59 2014, 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 May 6 16:06:33 2014, 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 May 5 21:07:48 2014, 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 Apr 28 22:40:24 2014, 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.

     

    Error: not logged in

     

     

    Follow 12 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue May 20 21:29:30 2014pepetoStatusReady For Test=>Fixed
      Open/ClosedOpen=>Closed
    Sun May 18 21:24:20 2014pepetoAssigned toNone=>pepeto
    Wed May 14 09:47:24 2014pepetoAttached File-=>Added TEST.serv, #20737
    Tue May 13 21:25:10 2014cazfiAttached File-=>Added regression.serv, #20733
    Tue May 6 21:34:59 2014cazfiCategoryNone=>general
      Planned Release=>2.6.0
    Tue May 6 16:06:33 2014pepetoAttached File-=>Added genhash2.diff, #20663
      StatusIn Progress=>Ready For Test
    Mon May 5 21:07:48 2014pepetoAttached File-=>Added genhash.diff, #20644
      StatusNone=>In Progress
    Tue Apr 29 07:44:36 2014pepetoCarbon-Copy-=>Added -unavailable-
    Show feedback again

    Back to the top


    Powered by Savane 3.1-cleanup