Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 13 Next capture
2021 2022 2023
2 captures
13 Jun 22 - 14 Jun 22
sparklines
Close Help
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
0
Question by whydoidoit · Aug 23, 2013 at 12:27 PM · endless loop

Problem with HashSet

So I'm having a problem with the implementation of HashSet getting stuck in an endless loop working through it's internal implementation which uses a linked list. For some reason the list is getting linked back to itself after a resize operation or a series of removal and resize operations.

Basically it jams up in anywhere the linked list is used. E.g. this becomes an endless loop:

  bool SlotsContainsAt(int index, int hash, T item)
         {
             int current = table[index] - 1;
             while (current != NO_SLOT)
             {
                 Link link = links[current];
                 if (link.HashCode == hash && ((hash == HASH_FLAG && (item == null || null == slots[current])) ? (item == null && null == slots[current]) : comparer.Equals(item, slots[current])))
                     return true;
 
                 current = link.Next;
             }
 
             return false;
         }

So I believe this only happens after a resize operation or a significant number of removals. I can't work out what's wrong though - I've built my own version from the Mono source and added some debugging, here's the original:

    void Resize()
     {
         int newSize = HashPrimeNumbers.ToPrime((table.Length << 1) | 1);

         // allocate new hash table and link slots array
         var newTable = new int[newSize];
         var newLinks = new Link[newSize];

         for (int i = 0; i < table.Length; i++)
         {
             int current = table[i] - 1;
             while (current != NO_SLOT)
             {
                 int hashCode = newLinks[current].HashCode = GetItemHashCode(slots[current]);
                 int index = (hashCode & int.MaxValue) % newSize;
                 newLinks[current].Next = newTable[index] - 1;
                 newTable[index] = current + 1;
                 current = links[current].Next;
             }
         }

         table = newTable;
         links = newLinks;

         // allocate new data slots, copy data
         var newSlots = new T[newSize];
         Array.Copy(slots, 0, newSlots, 0, touched);
         slots = newSlots;

         threshold = (int)(newSize * DEFAULT_LOAD_FACTOR);
     }

And here's my debug version that does show that it is trying to link to itself just before my endless loop happens:

     void Resize()
     {
         int newSize = HashPrimeNumbers.ToPrime((table.Length << 1) | 1);

         // allocate new hash table and link slots array
         var newTable = new int[newSize];
         var newLinks = new Link[newSize];

         for (int i = 0; i < table.Length; i++)
         {
             int current = table[i] - 1;
             while (current != NO_SLOT)
             {
                 int hashCode = links[current].HashCode;
                 int index = (hashCode & int.MaxValue) % newSize;
                 if (newTable[index] != current+1)
                 {
                     newLinks[current].Next = newTable[index] - 1; //NO_SLOT the first time
                 }
                 else
                 {
                     UnityEngine.Debug.LogError("HashSet::Trying to link to self");
                 }
                 newTable[index] = current + 1;
                 current = links[current].Next;
             }
         }

         table = newTable;
         links = newLinks;

         // allocate new data slots, copy data
         var newSlots = new T[newSize];
         Array.Copy(slots, 0, newSlots, 0, touched);
         slots = newSlots;

         threshold = (int)(newSize * DEFAULT_LOAD_FACTOR);
     }
Comment
Add comment · Show 2
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image whydoidoit · Aug 23, 2013 at 12:27 PM 0
Share

@Bunny83 - sounds like one for you if you can spare the time!

avatar image whydoidoit · Aug 23, 2013 at 12:30 PM 0
Share

Also note, even though I'm trying to break the endless loop with that modified code, I don't seem to be successful - so perhaps something else is screwed up. I can only think that this would imply multiple entries in the slots list pointing to different items, or the hashcodes messing up somewhere.

1 Reply

· Add your reply
  • Sort: 
avatar image
0
Best Answer

Answer by whydoidoit · Aug 23, 2013 at 02:39 PM

Ah turned out to be a multithreading issue that only occurs in the Editor.

Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this Question

Answers Answers and Comments

15 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

Animation Won't Stop Looping 1 Answer

Showing a second ObjectPicker as soon as the first one closes freezes the editor 0 Answers

Endless runner, road segments spawn speed 0 Answers

Coroutine while(bool) kills Unity 1 Answer

Unwanted lines in endless 3D game 2 Answers


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges