Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 15.07.10 14:40
Оценка:
Протестировал кое какие нюансы с GetHashCode с целью оптимизации участка, где много обращений к Dictionary — получение значения по ключу, добавление элементов по ключу и тд.
Получилось чтото непонятное.

Release

Test20 GetHashCode default
3,062461
Test21 GetHashCode from string
0,540457
Test22 GetHashCode overrided, fixed value
0,4687002
Test23 GetHashCode inherited default
2,747097
Test24 GetHashCode cashed default
0,4954112


Единицы измерения не важны, получены с пом. QueryPerformanceCounter, кол-во запусков контрольных участков >1000000

По результатам выходит что дефолтный метод работает медленнее чем он же унаследованый
Унаследованый кешированый работает намного быстрее, следовательно дефолтный ничего не кеширует и вычисляет значение постоянно

Вопрос 1 — почему дефолтный работает медленно, если коде ротора вроде как есть кеширование значения в дефолтной реализации ?

Вопрос 2 — почему метод работает примерно так же как и с кешированием, хотя в коде для строки нет никакого кеширования ?.

P.S. 4.0 дефотный работает чуть быстрее чем 3.5, процентов на 10

Тесты, классы и вычисление хешкода для строки

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public override unsafe int GetHashCode()
{
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}


        [NamedTest("GetHashCode default")]
        private static void Test20()
        {
            object o = new HashCodeWrapper(new object());

            for (int j = 0; j < Count; j++)
            {
                i ^= o.GetHashCode();
            }
        }

        [NamedTest("GetHashCode from string")]
        private static void Test21()
        {
            object s = new HashCodeWrapper("345");



            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }

        [NamedTest("GetHashCode overrided, fixed value")]
        private static void Test22()
        {
            object s = new HashCodeWrapper(new Suxx2(123));

            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }

        [NamedTest("GetHashCode inherited default")]
        private static void Test23()
        {
            object s = new HashCodeWrapper(new Suxx());

            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }

        [NamedTest("GetHashCode cashed default")]
        private static void Test24()
        {
            object s = new HashCodeWrapper(new Suxx3());

            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }


    class Suxx
    {
        private RectangleF rectf;
        private readonly int _hashCode;
    }

    class Suxx3
    {
        private RectangleF rectf;
        private int _hashCode = 0;

        public override int GetHashCode()
        {
            if (_hashCode == 0)
                _hashCode = base.GetHashCode();

            return _hashCode;
        }
    }
    class Suxx2
    {
        private RectangleF rectf;
        private readonly int _hashCode;

        public Suxx2(int hashCode)
        {
            _hashCode = hashCode;
        }

        public override int GetHashCode()
        {
            return _hashCode;
        }
    }

    class SuxxD
    {
        private RectangleD rectd;
    }

    struct RectangleD
    {
        public double X;
        public double Y;
        public double Width;
        public double Height;
    }

    class HashCodeWrapper
    {
        private readonly object _o;

        public HashCodeWrapper(object o)
        {
            _o = o;
        }

        public override int GetHashCode()
        {
            return _o.GetHashCode();
        }
    }
Re: Непонятное с GetHashCode
От: TK Лес кывт.рф
Дата: 15.07.10 15:16
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>Вопрос 1 — почему дефолтный работает медленно, если коде ротора вроде как есть кеширование значения в дефолтной реализации ?

Вы время на кеширование в своих тестах тоже замеряете или оно исключается из финальных результатов?
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re[2]: Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 15.07.10 18:36
Оценка:
Здравствуйте, TK, Вы писали:

I>>Вопрос 1 — почему дефолтный работает медленно, если коде ротора вроде как есть кеширование значения в дефолтной реализации ?

TK>Вы время на кеширование в своих тестах тоже замеряете или оно исключается из финальных результатов?

Замеряю конечно же
Re: Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 16.07.10 12:36
Оценка:
Здравствуйте, Ikemefula, Вы писали:

Если у кого есть желание, вот файл для запуска. Буду весьма признателен за помощь !

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Linq.Expressions;
using System.Runtime.ConstrainedExecution;
using System.Runtime.InteropServices;
using System.Text;

namespace ConsoleApplication1
{
    [AttributeUsage(AttributeTargets.Method, AllowMultiple = false)]
    class NamedTestAttribute : Attribute
    {
        public NamedTestAttribute(string name)
        {
            Name = name;
        }

        public string Name { get; private set; }
    }

    class Suxx
    {
        private RectangleF rectf;
        private readonly int _hashCode;
   }
    class Suxx3
    {
        private RectangleF rectf;
        private int _hashCode = 0;

        public override int GetHashCode()
        {
            if (_hashCode == 0)
                _hashCode = base.GetHashCode();

            return _hashCode;
        }
    }
    class Suxx2
    {
        private RectangleF rectf;
        private readonly int _hashCode;

        public Suxx2(int hashCode)
        {
            _hashCode = hashCode;
        }

        [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
        public override int GetHashCode()
        {
            return _hashCode;
        }
    }

    class SuxxD
    {
        private RectangleD rectd;
    }

    struct RectangleD
    {
        public double X;
        public double Y;
        public double Width;
        public double Height;
    }

    class HashCodeWrapper
    {
        private readonly object _o;

        public HashCodeWrapper(object o)
        {
            _o = o;
        }

        public override int GetHashCode()
        {
            return _o.GetHashCode();
        }
    }


    class Program
    {

        private static int i = 0;
        const int Count = 3000000;

        static void Main(string[] args)
        {

            Test(() => Test20());
            Test(() => Test21());
            Test(() => Test22());
            Test(() => Test23());
            Test(() => Test24());
            //Test(() => Test11());
            //Test(() => Test12());
            //Test(() => Test13());
            //Test(() => Test14());
            //Test(() => Test15());
            //Test(() => Test16());
            //Test(() => Test17());
            //Test(() => Test18());
            //Test(() => Test1());
            //Test(() => Test2());
            //Test(() => Test3());
            //Test(() => Test4());
            //Test(() => Test5());
            //Test(() => Test6());
            //Test(() => Test7());
            //Test(() => Test8());
            //Test(() => Test9());
            Console.WriteLine(i);
            Console.ReadLine();
        }

        private static void Test(Expression<Action> action)
        {
            Action compiled = action.Compile();

            var method = (action.Body as MethodCallExpression).Method;
            var attribute = method.GetCustomAttributes(true)
                .OfType<NamedTestAttribute>()
                .FirstOrDefault();
            string name = method.Name + " ";

            if (attribute != null)
                name += attribute.Name;


            Console.WriteLine(name);

            using (new PerfCounter(1, v => Console.WriteLine(" " + v)).Start())
            {
                for (int j = 0; j < 10; j++)
                {
                    compiled();
                }
                GC.Collect();
                GC.Collect();
                GC.Collect();
                GC.Collect();
            }
        }

        [NamedTest("GetHashCode default")]
        private static void Test20()
        {
            object o = new HashCodeWrapper(new object());

            for (int j = 0; j < Count; j++)
            {
                i ^= o.GetHashCode();
            }
        }

        [NamedTest("GetHashCode from string")]
        private static void Test21()
        {
            object s = new HashCodeWrapper("345");



            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }

        [NamedTest("GetHashCode overrided, fixed value")]
        private static void Test22()
        {
            object s = new HashCodeWrapper(new Suxx2(123));

            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }

        [NamedTest("GetHashCode inherited default")]
        private static void Test23()
        {
            object s = new HashCodeWrapper(new Suxx());

            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }

        [NamedTest("GetHashCode cashed default")]
        private static void Test24()
        {
            object s = new HashCodeWrapper(new Suxx3());

            for (int j = 0; j < Count; j++)
            {
                i ^= s.GetHashCode();
            }
        }


        [NamedTest("GetHashCode default, fill")]
        private static void Test11()
        {
            Dictionary<object, object> hash = new Dictionary<object, object>();
            Rnd rnd = new Rnd(Count);

            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                hash[new Suxx()] = null;
            }
        }

        [NamedTest("GetHashCode custom, fill")]
        private static void Test12()
        {
            Dictionary<object, object> hash = new Dictionary<object, object>();
            Rnd rnd = new Rnd(Count);


            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                hash[new Suxx2(hashCode)] = null;
            }
        }


        [NamedTest("GetHashCode default, fill, HashTable")]
        private static void Test13()
        {
            Hashtable hash = new Hashtable();
            Rnd rnd = new Rnd(Count);

            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                hash[new Suxx()] = null;
            }
        }

        [NamedTest("GetHashCode custom, fill, HashTable")]
        private static void Test14()
        {
            Hashtable hash = new Hashtable();
            Rnd rnd = new Rnd(Count);


            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                hash[new Suxx2(hashCode)] = null;
            }
        }

        [NamedTest("GetHashCode default, fill, extract")]
        private static void Test15()
        {
            Dictionary<object,object > hash = new Dictionary<object, object>();
            Rnd rnd = new Rnd(Count);
            List<Suxx> list = new List<Suxx>(Count);

            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                Suxx suxx = new Suxx();

                hash[suxx] = null;
                list.Add(suxx);
            }

            foreach (var suxx in list)
            {
                object o = hash[suxx];
            }
        }


        [NamedTest("GetHashCode custom, fill, extract")]
        private static void Test16()
        {
            Dictionary<object,object > hash = new Dictionary<object, object>();
            Rnd rnd = new Rnd(Count);
            List<Suxx2> list = new List<Suxx2>(Count);


            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                Suxx2 suxx = new Suxx2(hashCode);

                hash[suxx] = null;
                list.Add(suxx);

            }

            foreach (var suxx in list)
            {
                object o = hash[suxx];
            }
        }

        [NamedTest("GetHashCode default, fill, extract, Hashtable")]
        private static void Test17()
        {
            Hashtable hash = new Hashtable();
            Rnd rnd = new Rnd(Count);
            List<Suxx> list = new List<Suxx>(Count);

            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                Suxx suxx = new Suxx();

                hash[suxx] = null;
                list.Add(suxx);
            }

            foreach (var suxx in list)
            {
                object o = hash[suxx];
            }
        }


        [NamedTest("GetHashCode custom, fill, extract, Hashtable")]
        private static void Test18()
        {
            Hashtable hash = new Hashtable();
            Rnd rnd = new Rnd(Count);
            List<Suxx2> list = new List<Suxx2>(Count);


            for (int j = 0; j < Count; j++)
            {
                int hashCode = rnd[j];

                Suxx2 suxx = new Suxx2(hashCode);

                hash[suxx] = null;
                list.Add(suxx);

            }

            foreach (var suxx in list)
            {
                object o = hash[suxx];
            }
        }


        [NamedTest("Create objects")]
        private static void Test1()
        {
            //List<object> list = new List<object>(10000000);

            for (int j = 0; j < Count; j++)
            {
                Object obj = new object();

                Boxing(obj);
            }
        }

        [NamedTest("Create RectangleF, box")]
        private static void Test2()
        {
            //List<object> list = new List<object>(10000000);

            for (int j = 0; j < Count; j++)
            {
                RectangleF obj = new RectangleF();

                Boxing(obj);
            }
        }

        [NamedTest("Create RectangleF, box+unbox")]
        private static void Test3()
        {
            //List<RectangleF> list = new List<RectangleF>(10000000);

            for (int j = 0; j < Count; j++)
            {
                RectangleF obj = new RectangleF();

                BoxingUnboxing(obj);
            }
        }

        [NamedTest("Create RectangleF, No box+unbox, copy result")]
        private static void Test4()
        {
            //List<RectangleF> list = new List<RectangleF>(10000000);

            for (int j = 0; j < Count; j++)
            {
                RectangleF obj = new RectangleF();

                RectangleF obj2 = None(obj);
            }
        }

        [NamedTest("Create class with embedded RectangleF")]
        private static void Test5()
        {
            //List<Suxx > list = new List<Suxx>(10000000);

            for (int j = 0; j < Count; j++)
            {
                Suxx obj = new Suxx();

                Boxing(obj);
            }
        }

        [NamedTest("Create RectangleD, No box+unbox, copy result")]
        private static void Test6()
        {
            //List<Suxx > list = new List<Suxx>(10000000);

            for (int j = 0; j < Count; j++)
            {
                RectangleD obj = new RectangleD();

                RectangleD obj2 = None(obj);
            }
        }

        [NamedTest("Create RectangleD, copy")]
        private static void Test7()
        {
            //List<Suxx > list = new List<Suxx>(10000000);

            for (int j = 0; j < Count; j++)
            {
                RectangleD obj = new RectangleD();
                RectangleD obj2 = obj; 

                
            }
        }

        [NamedTest("Create class with embedded RectangleD")]
        private static void Test8()
        {
            //List<Suxx > list = new List<Suxx>(10000000);

            for (int j = 0; j < Count; j++)
            {
                SuxxD obj = new SuxxD();

                Boxing(obj);
            }
        }

        [NamedTest("Create RectangleD, by ref")]
        private static void Test9()
        {
            //List<Suxx > list = new List<Suxx>(10000000);

            for (int j = 0; j < Count; j++)
            {
                RectangleD obj = new RectangleD();

                None(ref obj);
            }
        }

        private static void None(ref RectangleD rc)
        {
            
        }

        private static RectangleD None(RectangleD rc)
        {
            //rc.X += 1;

            return rc;
        }

        private static RectangleF None(RectangleF rc)
        {
            //rc.X += 1;

            return rc;
        }

        private static RectangleF BoxingUnboxing(object obj)
        {
            RectangleF rect = (RectangleF)obj;

            //rect.X += 1;

            return rect;
        }

        private static object Boxing(object o)
        {
            //i += o.GetHashCode();

            return o;
        }
    }

    internal class Rnd
    {
        private int[] _numbers;

        public Rnd(int count)
        {
            _numbers=  new int[count];

            Random random = new Random();

            for (int i = 0; i < _numbers.Length; i++)
            {
                _numbers[i] = random.Next();
            }
        }

        public int this[int i]
        {
            get { return _numbers[i]; }
        }
    }

    public struct PerfCounter : IDisposable
    {
        Int64 _start;
        readonly float _koef;
        private readonly Action<float> _lambda;

        public PerfCounter(float koef):this(koef,null)
        {
        }
        public PerfCounter(float koef, Action<float> l)
        {
            _start = 0;
            _koef = koef;
            _lambda = l;
        }

        public PerfCounter Start()
        {
            _start = 0;
            QueryPerformanceCounter(ref _start);

            return this;
        }

        public float Finish()
        {
            Int64 finish = 0;
            QueryPerformanceCounter(ref finish);

            Int64 freq = 0;
            QueryPerformanceFrequency(ref freq);
            return (finish - _start) / (freq / _koef);
        }

        [DllImport("Kernel32.dll")]
        static extern bool QueryPerformanceCounter(ref Int64 performanceCount);

        [DllImport("Kernel32.dll")]
        static extern bool QueryPerformanceFrequency(ref Int64 frequency);

        public void Dispose()
        {
            if (_lambda != null)
                _lambda(Finish());
        }
    }
}
Re[2]: Непонятное с GetHashCode
От: samius Япония http://sams-tricks.blogspot.com
Дата: 16.07.10 13:09
Оценка: 12 (1)
Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, Ikemefula, Вы писали:

I>Если у кого есть желание, вот файл для запуска. Буду весьма признателен за помощь !

Test20 GetHashCode default
 0,245965
Test21 GetHashCode from string
 0,3033084
Test22 GetHashCode overrided, fixed value
 0,1558347
Test23 GetHashCode inherited default
 0,2425851
Test24 GetHashCode cashed default
 0,1785424
Re[3]: Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 16.07.10 14:41
Оценка:
Здравствуйте, samius, Вы писали:

S>
S>Test20 GetHashCode default
S> 0,245965
S>Test21 GetHashCode from string
S> 0,3033084
S>Test22 GetHashCode overrided, fixed value
S> 0,1558347
S>Test23 GetHashCode inherited default
S> 0,2425851
S>Test24 GetHashCode cashed default
S> 0,1785424
S>


Это вобщем то и ожидалось. Что у тебя за проц, частота, ядра, кеш, память, частота шины, версия фреймворка, системы ?

Не ясно только, как GetHashCode у строки получается таким шустрым.

Вот результаты с других компов, как их объяснить, я не знаю

Test20 GetHashCode default
 3.421309
Test21 GetHashCode from string
 0.5374046
Test22 GetHashCode overrided, fixed value
 0.4074513
Test23 GetHashCode inherited default
 3.004157
Test24 GetHashCode cashed default
 0.3679777


Test20 GetHashCode default
 1.514012
Test21 GetHashCode from string
 0.2032812
Test22 GetHashCode overrided, fixed value
 0.1167166
Test23 GetHashCode inherited default
 1.506943
Test24 GetHashCode cashed default
 0.1340586
Re[4]: Непонятное с GetHashCode
От: samius Япония http://sams-tricks.blogspot.com
Дата: 16.07.10 15:40
Оценка: 12 (1)
Здравствуйте, Ikemefula, Вы писали:

I>Это вобщем то и ожидалось. Что у тебя за проц, частота, ядра, кеш, память, частота шины, версия фреймворка, системы ?

Intel Core 2 Duo E6600, 2,4 GHz, 2 ядра, 4Mb L2, Bus 266MHz, не разогнанный
4 X PC2-6400(400MHz),
Win7
.NET FW 4

I>Не ясно только, как GetHashCode у строки получается таким шустрым.

Похоже на то что GetHashCode у object-а медленный. Сделай строку посерьезнее...
Re[5]: Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 16.07.10 19:36
Оценка:
Здравствуйте, samius, Вы писали:

S>Intel Core 2 Duo E6600, 2,4 GHz, 2 ядра, 4Mb L2, Bus 266MHz, не разогнанный
S>4 X PC2-6400(400MHz),
S>Win7
S>.NET FW 4

Спасибо. Я проверял на трех компах, расклад получается примерно один и тот же, дефолтная реализация в три-пять раз медленнее простого вычисления.

I>>Не ясно только, как GetHashCode у строки получается таким шустрым.

S>Похоже на то что GetHashCode у object-а медленный. Сделай строку посерьезнее...

Вроде как со строкой нет разницы
Re: Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 17.07.10 13:46
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>Протестировал кое какие нюансы с GetHashCode с целью оптимизации участка, где много обращений к Dictionary — получение значения по ключу, добавление элементов по ключу и тд.
I>Получилось чтото непонятное.

I>

I>Release

I>Test20 GetHashCode default
I> 3,062461
I>Test21 GetHashCode from string
I> 0,540457
I>Test22 GetHashCode overrided, fixed value
I> 0,4687002
I>Test23 GetHashCode inherited default
I> 2,747097
I>Test24 GetHashCode cashed default
I> 0,4954112

Все непонятные вещи вроде стали понятными — GetHashCode у строки не кешируется, вроде samius подсказал, а я все равно тупил

Соответсвенно нужно быть осторожно с объектами, которые сравниваются по значению, GetHashCode для оных нужно писать очень аккуратно, ибо издержки на вычисления оного кода могут быть практически любыми, вплоть до того, что надобность в Dictionary исчезает
Re[2]: Непонятное с GetHashCode
От: samius Япония http://sams-tricks.blogspot.com
Дата: 17.07.10 18:07
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>Соответсвенно нужно быть осторожно с объектами, которые сравниваются по значению, GetHashCode для оных нужно писать очень аккуратно, ибо издержки на вычисления оного кода могут быть практически любыми, вплоть до того, что надобность в Dictionary исчезает

Dictionary<TKey,TValue> хэшкод как раз кэширует и вычисляет лишь однажды при каждой операции. Чем GetHashCode можно так нагрузить чтобы аж словарь просел?
Re[3]: Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 17.07.10 18:54
Оценка:
Здравствуйте, samius, Вы писали:

S>Dictionary<TKey,TValue> хэшкод как раз кэширует и вычисляет лишь однажды при каждой операции. Чем GetHashCode можно так нагрузить чтобы аж словарь просел?
Словарь кеширует для того, что бы можно было размер внутреннего массива менять.

А вот при обращении например чз ContainsKey у объекта по любому запрашивается хешкод который в этот момент и вычисляется заново.

Вычисление хешкода для строки — долгая операция. Чем длиннее строка, тем меньше преимуществ у Dictionary перед List.
Re[4]: Непонятное с GetHashCode
От: samius Япония http://sams-tricks.blogspot.com
Дата: 17.07.10 19:34
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, samius, Вы писали:

S>>Dictionary<TKey,TValue> хэшкод как раз кэширует и вычисляет лишь однажды при каждой операции. Чем GetHashCode можно так нагрузить чтобы аж словарь просел?
I>Словарь кеширует для того, что бы можно было размер внутреннего массива менять.

I>А вот при обращении например чз ContainsKey у объекта по любому запрашивается хешкод который в этот момент и вычисляется заново.
Да, я и написал что однажды на операцию.

I>Вычисление хешкода для строки — долгая операция. Чем длиннее строка, тем меньше преимуществ у Dictionary перед List.
Сравнение строк тоже небыстрая операция, еще неизвестно, что дороже для длинной строки, взять ее хэшкод или сравнить ее с идентичной, либо отличающейся в хвосте...
Т.е. либо раз взять хэшкод и несколько раз сравнить (в среднем нужно одно сравнение) при работе со словарем, либо n раз сравнивать при работе со списком. Притом при нахождении идентичной строки однажды случится полное сравнение и в том и в другом случае. Получается что одно взятие хэшкода против O(n) неполных сравнений.
Re[2]: Непонятное с GetHashCode
От: andy1618 Россия  
Дата: 17.07.10 19:51
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>Если у кого есть желание, вот файл для запуска. Буду весьма признателен за помощь !

I>
I>        const int Count = 3000000;
...
I>        [NamedTest("GetHashCode default, fill, extract")]
I>        private static void Test15()
I>        {
I>            Dictionary<object,object > hash = new Dictionary<object, object>(); // <- Вот тут очень не помешает Count в скобках.
I>            List<Suxx> list = new List<Suxx>(Count);
...
I>    }
I>}
I>


Небольшой комментарий по коду, не относящийся непосредственно к хешированию:
при инициализации Dictionary и HashTable тоже крайне желательно проставлять Capacity, как и для списков.
Иначе в процессе добавления элементов в эти контейнеры их внутренняя хеш-таблица будет несколько раз заново перестраиваться.
Re[5]: Непонятное с GetHashCode
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 17.07.10 20:59
Оценка:
Здравствуйте, samius, Вы писали:

S>Т.е. либо раз взять хэшкод и несколько раз сравнить (в среднем нужно одно сравнение) при работе со словарем, либо n раз сравнивать при работе со списком. Притом при нахождении идентичной строки однажды случится полное сравнение и в том и в другом случае. Получается что одно взятие хэшкода против O(n) неполных сравнений.

Это и ежу понятно.

Речь о том, что GetHashCode медленнее намного, чем Equals.

На длинных строках список из двух-трех десятков строк будет работать быстрее нежели Dictionary.

А на огромных строках возможно и сотня элементов в списке будет проверяться быстрее.
Re[4]: Непонятное с GetHashCode
От: Mr.Cat  
Дата: 17.07.10 23:23
Оценка:
Здравствуйте, Ikemefula, Вы писали:
I>Вот результаты с других компов, как их объяснить, я не знаю
I>
I>Test20 GetHashCode default
I> 3.421309
I>Test21 GetHashCode from string
I> 0.5374046
I>Test22 GetHashCode overrided, fixed value
I> 0.4074513
I>Test23 GetHashCode inherited default
I> 3.004157
I>Test24 GetHashCode cashed default
I> 0.3679777
I>

I>
I>Test20 GetHashCode default
I> 1.514012
I>Test21 GetHashCode from string
I> 0.2032812
I>Test22 GetHashCode overrided, fixed value
I> 0.1167166
I>Test23 GetHashCode inherited default
I> 1.506943
I>Test24 GetHashCode cashed default
I> 0.1340586
I>


У меня в целом та же фигня. Core i5, win 7, fw4. Интересно было бы посмотреть, что там внутри у Object.GetHashCode().
Re[5]: Непонятное с GetHashCode
От: _FRED_ Черногория
Дата: 17.07.10 23:58
Оценка: 2 (1)
Здравствуйте, Mr.Cat, Вы писали:

MC>…Интересно было бы посмотреть, что там внутри у Object.GetHashCode().

А зачем? В тех местах, где производительность GetHashCode() является значимой (или хотя бы мало-мальски интересной) величиной, необходимо этот метод переопределить (или определить свой провайдер или equality comparer). "Дефолтовая" же реализация имеет право (и об этом прямо сказано в документации) может меняться от версии к версии.
Help will always be given at Hogwarts to those who ask for it.
Re[6]: Непонятное с GetHashCode
От: andy1618 Россия  
Дата: 18.07.10 03:45
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>Речь о том, что GetHashCode медленнее намного, чем Equals.

В общем случае — да (и понятно почему). Хотя, ничто не мешает для конкретного
случая написать свою упрощённую хеш-функцию. Например, для небольшого набора строк,
вариантных по длине, даже примитивнейший хеш — длина строки — будет давать
приемлемо низкий процент коллизий.


I>На длинных строках список из двух-трех десятков строк будет работать быстрее нежели Dictionary.
I>А на огромных строках возможно и сотня элементов в списке будет проверяться быстрее.

Логично. Чем сложнее подход, тем, в общем случае, на более "крутые" случаи он рассчитан.
К примеру, простейшая сортировка вставками со средней сложностью O(N^2) на небольших входных
массивах легко уделает более громоздкий квиксорт с его средней сложностью O(N*logN).
Re[6]: Непонятное с GetHashCode
От: Mr.Cat  
Дата: 18.07.10 10:44
Оценка:
Здравствуйте, _FRED_, Вы писали:
_FR>А зачем?
А зачем вообще знание того, как внутри работает тот или иной метод? Вот, например, строка не запоминает свой хэш — это по-твоему полезное знание? Кому-то нравится программировать под черный ящик, кому-то нет.

_FR>В тех местах, где производительность GetHashCode() является значимой (или хотя бы мало-мальски интересной) величиной, необходимо этот метод переопределить (или определить свой провайдер или equality comparer).
Капитан, вы?

_FR>"Дефолтовая" же реализация имеет право (и об этом прямо сказано в документации) может меняться от версии к версии.
И что дальше?

PS: Если в msdn напишут, что надо в окно прыгнуть — ты прыгнешь?
Re[7]: Непонятное с GetHashCode
От: _FRED_ Черногория
Дата: 18.07.10 11:52
Оценка:
Здравствуйте, Mr.Cat, Вы писали:

_FR>>А зачем?
MC>А зачем вообще знание того, как внутри работает тот или иной метод?

Сказано же, что реализация может меняться (и меняется) от версии к версии. Вам все варианты "как" интересны или любой подойдёт? Если бы было хоть чуточку интересно, то нашли бы уже первую подсказку. А дальше — как в романах Дэна Брауна

MC>Вот, например, строка не запоминает свой хэш — это по-твоему полезное знание? Кому-то нравится программировать под черный ящик, кому-то нет.

Например, для строки хеш часто вообще неправильно (точнее, не лучшим, совсем не рациональным, грозящим многими коллизиями, образом) высчитывается. Но строка — это не Object, GetHashCode() которой настоятельно рекомендуют переопределять. Поэтому сравнение знания о том, как считается хэш у строки и у Object не является корректным.

В данном конкретном случае — дефолтовая реализация есть ни что иное как совершенно бесполезное знание. Да вот и коментарии об этом же говорят:
// Objects (& especially value classes) should override this method.

Желание узнать эту реализацию сродни желанию узнать, видит ли белый коридор человек перед смертью.

_FR>>В тех местах, где производительность GetHashCode() является значимой (или хотя бы мало-мальски интересной) величиной, необходимо этот метод переопределить (или определить свой провайдер или equality comparer).
MC>Капитан, вы?

Спасибо вам за высказывание вашего мнения о моей личности. Для меня это очень ценно.

_FR>>"Дефолтовая" же реализация имеет право (и об этом прямо сказано в документации) может меняться от версии к версии.
MC>И что дальше?
MC>PS: Если в msdn напишут, что надо в окно прыгнуть — ты прыгнешь?

А вам непременно надо знать, что испытывают гомосеки? Тогда в чём заключается сложность? Запускайте программу, подключайте отладчик и изучайте. Не думаю, что ответ на ваш вопрос интересен на столько, что бы найти его.
Help will always be given at Hogwarts to those who ask for it.
Re[8]: Непонятное с GetHashCode
От: Mr.Cat  
Дата: 18.07.10 14:03
Оценка:
Здравствуйте, _FRED_, Вы писали:
_FR>http://stackoverflow.com/questions/720177/default-implementation-for-object-gethashcode
На ротор еще ТС ссылался, но по нему пока непонятно, почему в одном и том же коде у кого-то хэш кэшируется эффективно, а у кого-то нет. Есть какие-нить предположения?

MC>>Вот, например, строка не запоминает свой хэш — это по-твоему полезное знание?
_FR>Например ... не является корректным.
Будем считать, что это было длинное "да"?

_FR>
// Objects (& especially value classes) should override this method.

Ну вот ТС наоборот (вроде как) не нужно переопределять. Не догма же.

MC>>PS: Если в msdn напишут, что надо в окно прыгнуть — ты прыгнешь?
_FR>А вам непременно надо знать, что испытывают гомосеки?
Эээ?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.