Jump to content
  • Advertisement

ahmadierfan99

Member
  • Content Count

    6
  • Joined

  • Last visited

Posts posted by ahmadierfan99


  1.  

    Quote

     When the time comes that you need to make changes

    I heard you, I couldn't agree more.

    I completely ignored that you have to profile your app constantly and make changes; Because deep down in my mind I had to start writing everything the best version which is pure nonsense and impossible.

    I have other questions for you about your experiences on the projects you've worked on

    Since you might have had to ship your application on multiple hardwares and operating systems, 

    1. Which Hardware(s) did you run your app on and how important was that? 

    I ask you this because in your previous replies I understood an algorithm performance and superiority to other algorithms heavily depends on the hardware. 

    2. How did you budget your "subsystem's updates"?

    3. Was there a time which you had to refer to your code's compiled assembly or referred to CPU Instruction Cycles on your specific hardware to see the actual or estimated time needed to do a specific job?


  2. Quote

    So without any context, that same binary search might be roughly 1/4 the time of a linear search, or it might be 3x the time of a linear search, or anywhere in between.

    That's really amazing and I didn't think about it that way. Although in Games you know how big your data is going to be and you know the hardwares it's going to run on.

    Quote

    And with all of that, searches generally aren't the big bottlenecks of modern games.  They contribute to the processing time, but they aren't the big bottlenecks. 

    That's why It's more than a hobby project for me to learn more.

    There is a lot to learn from CPU's architectures and Assembly Language to Operating Systems and Compilers and a lot of other things.

    Thank you, It's been really helpful knowing there is a lot more about what I don't know and need to know before starting these kinds of projects and tests.

    Are there any other resources and practices you suggest to help me reason about the hardware better?


  3. 2 hours ago, Alberth said:

    There is no algorithm that outperforms all others in every case

    100% Agreed. That's why I'm looking for a specific case and data to work with which the results can't prove anything for other cases but with what @frob said the problem is there are different compilers and hardware. My Question is does that make much difference in modern CPU's and not worth doing the benchmark?

    Quote

    I do hope you realize that exploiting hardware to the limits is generally not going to win the war right? You win wars by having effective algorithms doing the work.

    0% Agreed Since our program runs on hardware It's definitely worth knowing modern CPU's and using them the best way we can.

    Here is a quote from dod book (which I recommend reading if you haven't)

    Quote

     

    you can see it uses a linear search instead of a binary search, and yet it still manages to make the original binary search look slow by comparison, and we must assume, as with most things on modern machines, it is because the path the code is taking is using the resources better, rather than being better in a theoretical way, or using fewer instructions.

    
    i5-4430 @ 3.00GHz
    Average 13.71ms [Full anim key - linear search]
    Average 11.13ms [Full anim key - binary search]
    Average  8.23ms [Data only key - linear search]
    Average  7.79ms [Data only key - binary search]
    Average  1.63ms [Pre-indexed - binary search]
    Average  1.45ms [Pre-indexed - linear search]

     

    
     

    With this in mind, I know there is no general solution to everything that would be the opposite of my beliefs which is data-oriented, BUT there are some aspects of modern hardware that are very similar and we can use the best from It.

     

    Honestly, with what @frob said so far which is really helpful. I'm in doubt to continue this project for my learning purposes and I don't think(doubt) it's useless and not worth looking at when it's done

     

    
     

  4. Well now I know what I'm going to do thanks to you.

    I'm hoping to practice and challenge my self to optimize algorithms on my CPU and try to understand the modern hardware better than before and try on different CPUs and Compilers to see the differences and learn as much as possible.

    Thank you for setting my mindset.

    And do you believe that in the range of today's modern CPUs, if an algorithm is better than the other, it also performs better on other similar hardwares?

    Or do you believe it's possible the results can be reversed changing from 8300 to 8400 (same Cache Line size)?

     

     


  5. Thank you very much @frob.

    You're right and I know most of the things you pointed out.

    It's mostly personal for me but I'll definitely talk to other more professional than me to and consult them about publishing it, if I wanted to.

    You're right but there is a finite set of hardware I'm targeting and as always the most important aspect of any program is hardware since it's the actual platform.

    In my mind the first try is MSVC and yes there are difference between compilers and optimizations they do.

    I will definitely test GCC, Clang and other compilers and thanks for pointing it out.

    Now I just want a challenging practical data to work with and not some toy data I come up with.

    Thanks 


  6. I'm writing a benchmark for on data-oriented search algorithms and data structures in full details when there is a high need for efficient searching each frame and about what to choose depending on

    1. How cache friendly it can be
    2. Algorithm's order
    3. Insertion/Deletion frequency (how often data needs to change each frame)

    I have these Data Structures in mind right now

    • Array (linear)
    • Binary search trees
    • B-trees
    • Red Black Trees
    • Hash Tables
    • Bloom Filters

    I'm looking for common data used in games or graphics programming that is frequently modified and searched for to complete my benchmark.

    Data-Oriented Book uses Simple Toy Animation Data to benchmark linear search and binary search but I believe there's some data more challenging.

     

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!