Tuesday, January 10, 2012

LINQ sorting is also vulnerable

This is a follow-up post to .Net's Sort Is Not Secure. Don't Use It. Here's a Better One.

A reader asked if LINQ's sort has the same vulnerability. I added tests for sorting an array using LINQ's 'orderby' clause. Another reader wondered if the Sort() method for generic lists had the same problem so I added that test as well.

Time required for sorting one million items provided by an adversary:

AlgorithmSorting Time
Zimbry Introsortone-half second
.Net CLR (Array)1,588 seconds
.Net CLR (LINQ)1,916 seconds
.Net CLR (List)1,588 seconds

Detailed benchmark results are here: Sorting up to 1 million items (with an adversary)

Notes on the test:

All tests were run under .Net framework version 4.0

The times reported in the table are an average of the times taken for one ascending sort and one descending sort.

50 comments:

  1. It's worth noting that nearly all cases of sorting 1 million items with LINQ in production code use a LINQ provider which delegates the sort to SQL, such as LINQ to Entities or LINQ to SQL.

    Sorting 1M (or any non-trivial number) objects in LINQ to Objects would be an obvious bug to anyone who bothers to profile their app that even with a very efficient sort it would be regarded as a bug.

    ReplyDelete
  2. Craig, I disagree. Perhaps in database applications, it's uncommon to keep a million or more objects in memory. But many types of applications that work with large amounts of data don't use SQL at all. Our apps, for example, get their data from a custom repository stream, from crawling the Web, and from sequential files of all types. We don't even have a SQL server. We're not exactly mainstream, true, but applications like ours aren't exactly rare, either.

    The LINQ sort, by the way, is particularly bad. Whereas the standard array sort has a median-of-three pivot selection and type-specific optimizations for base types, the LINQ sort is a standard naive QuickSort. Array.Sort won't exhibit pathological behavior with a sorted array. LINQ's sort will.

    ReplyDelete
  3. Jim, you're blaming the wrong code. It's not "LINQ" that's the problem here, it's "LINQ to Objects," which is a popular LINQ provider, indeed, but not 100% of LINQ, especially for "large-ish" results.

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. My TV is an Amazon program that offers a simple interface to the My TV service through Amazon's own websites and software programs. As previously noted, the program uses a simple web interface which enables the user to watch various television stations in the United States and Canada.

    For more information visit site :- www.amazon.com/mytv

    ReplyDelete

  6. Nice and well explained blog. Thanks for sharing these amazing thoughts
    PayPal Login
    Garmin Express

    ReplyDelete
  7. bellsouth email login
    Appreciative for this blog commenting grumblings. I think the supervisor of this site is truly making sure about for his site page since here every material is quality based material. bellsouth email login services are around the world and the no of users is growing by every passing day. Huge people from different locations in the world, bellsouth email login must be their. At times, due to some teechnical glitche, users cannot log in to their account. To help all Bellsouth account holders, here is this article that comprises bellsouth email login procedure, issues and it's’ easy fixes.
    for more info :- https://sites.google.com/view/att-bellsouth-email-login/home

    ReplyDelete
  8. Instantly play free online games, including solitaire, mahjong, hidden object, word, casino, card, and puzzle games. Play on your computer, tablet, or phone.

    pogo games sign in |
    www.pogo.com games |

    ReplyDelete
  9. For Venmo, QuickBooks, and yahoo mail login errors.

    venmo login |
    quickbooks login |
    yahoo mail login |

    ReplyDelete
  10. Looking for Cricket Balls? Buy Online Cricket Balls of All Sizes like Men, Youth, Boys, Kids and Junior Available at affordable price at NZ Cricket Store. We provide branded Cricket Accessories of best quality in New Zealand.

    ReplyDelete
  11. Watch anywhere, anytime, on an unlimited number of devices. Sign in with your Netflix account to watch instantly on the web at netflix
    Netflix Login
    tv.youtube.com/start

    ReplyDelete

  12. mcafee.com/activate - Find the McAfee antivirus download, install & activation steps. Enter McAfee activate code and get started at www.mcafee.com/activate.

    ReplyDelete
  13. Great thanks for sharing it had been very informative blog. A useful wording may be a good way to spotlight the many aspects of the subject keep it up. pluto.tv/activate | Netflix Party

    ReplyDelete
  14. This is very important Post, absolutely fantastic & very useful i really appreciate thanks for this Great Information.know about Paypal login Click the Link and Visit

    ReplyDelete
  15. For instant charles schwab login, go to the official page of #CharlesSchwab and tap on the “Log In” option. Then, enter your User ID and password for login.

    ReplyDelete
  16. quickbooks login makes online accounting easy. Log in to your QuickBooks Online account to keep track of the money you spend and to see how much money you are making.
    quickbooks unrecoverable error |
    quickbooks error 3371 |

    ReplyDelete
  17. Very nice post. Thanks for sharing the post. Best of Luck my dear friend.
    I like these kind of things .. I surely want something to contribute. is there any way for the same and check this too grammar checker -
    harvard referencing guide -case study help

    ReplyDelete
  18. This post is a most-awaited and informative. I am reading your article very enjoying it. Your good choice for the topic. You more articles written on other topics. I already some articles read but your article is very helpful to me.

    If you can change or set up the new printer, so you can visit our site. You easily set up the new printer with the help of this site: http//ij.start.canon

    ReplyDelete
  19. Really awesome blog. And thank you for sharing amazing information. This is a very useful post for me. This will absolutely be going to help me with my project. Thank you again . Know more about Slingshot Rental click the link and visit.

    ReplyDelete
  20. Amazon Prime is a paid streaming service that can be accessed online.www.amazon.com/mytvIt is available at. You have access to many services, including fast delivery, unlimited online video, movies online, and prime videos. Amazon Prime membership members can access instant video for free, or they can pay a fee to watch them.
    www.amazon.com/mytv
    www.amazon.com/mytv login
    amazon/mytv
    primevideo/mytv enter code
    paypal login

    ReplyDelete
  21. You can watch prime video online on smartphones, tablets, computers and smart TVs. To watch prime video online, you will need to enter the 6 digit Amazon activation code at www.amazon.com/mytv/primevideo.com/mytv. To sign in to your amazon account or create a new one using email and password, you can watch amazon prime episodes from your device.
    www.amazon.com/mytv enter code
    amazon.com/code
    primevideo/mytv enter code
    www.amazon.com/code
    amazon/mytv

    ReplyDelete
  22. www.amazon.com/mytv You have just received another Amazon device. What do you do? You will need to figure out how to connect your devices with Prime so that you can watch and tune into select Prime video content from anywhere. Simply create an amazon account and activate it using the amazon my TV activation code.
    paypal login
    www.amazon.com/code
    roku.com/link
    tubi.tv/activate
    espn.com/activate

    ReplyDelete
  23. Its an amazing website, really enjoy your articles. Helpful and interesting too. Keep doing this in future. I will support you. 카지노사이트

    ReplyDelete
  24. This post provided me with very helpful information. Are you interested in adding more information to your blog? Please visit my Check Webcam Online profile since it is more informative than my webcam profile.

    ReplyDelete
  25. Amazon Prime Video is the best platform to view the latest web series, movies and TV shows.Amazon.com/mytv. Amazon.com/mytv supports almost all devices. This includes Android and iOS devices. Amazon.com/mytv requires a high-speed internet connection and an amazon subscription. To resolve any issues during activation, users should contact customer service experts. To activate the service, users will need an amazon.com/mytv unique verification code. This article contains instructions on how to login to Amazon via.www.amazon.com/mytvThese guidelines will help you watch Amazon Prime Video free of charge.]
    Primevideo/mytv
    Primevideo/mytv enter code
    amazon.ca/redeem
    primevideo.com/mytv
    Primevideo/mytv


    ReplyDelete
  26. Amazon.com/mytvPrime is Amazon's paid subscription. It gives you unlimited access to many services, including fast delivery, unlimited streaming and exclusive deals. Unlimited streaming of TV shows and movies is available to Prime subscribers. Amazon Instant Video offers most of its content free of charge.Amazon Prime Membership.
    Primevideo/mytv
    Primevideo/mytv
    Primevideo/mytv
    Primevideo/mytv
    Primevideo/mytv

    ReplyDelete
  27. www.amazon.com/mytvYou can now watch Amazon Prime Videos on your TV and mobile devices. Amazon Prime members are eligible to receive unlimited access to thousands more Prime Video titles for no additional charge. ToAmazon Prime Video activationAfter signing in, you will receive an Amazon mytv code.Amazon.com/mytvEnter the amazon activation code in your smartphone or laptop
    Primevideo/mytv
    amazon.co.uk/mytv
    amazon.co.uk/mytv
    amazon.co.uk/mytv
    amazon.co.uk/mytv

    ReplyDelete
  28. ISO 9001 is the most common ISO standard, preferred by millions of organizations across the world. This generic standard specifies requirements for an organization’s Quality Management System to consistently provide products and services that satisfy customer requirements. This standard also helps the organizations to meet the applicable statutory and regulatory requirements. Most importantly, the ISO 9001 standard enhances customer satisfaction by continually improving the quality management system performance of the organization. ISO 9001 Certification in Turkey

    ReplyDelete
  29. Great thanks for sharing it had been very informative blog. A useful wording may be a good way to spotlight the many aspects of the subject keep it up. More info to visit: windows 10 activator | rip full form | cpu full form | psi full form.

    ReplyDelete
  30. Your post was fun to read. You will post soon, and I look forward to reading it. We wish you all the best with your future update. The article is interesting and helpful. Here is a profile about the writing tool you have been introduced to. By using this WPM typing test tool, we believe you will improve your typing skills.

    ReplyDelete
  31. Are you looking for places to eat Indian food nearby? Here you can explore the best Indian restaurants and cuisines near your location.Order now.

    https://www.adeenaskitchen.co.uk/menu

    ReplyDelete
  32. Thanks for sharing this wonderful piece of information.
    Stay up the good work!
    When you purchase a new http//ij.start.canon printer, it delivers good results and works smoothly.
    Sometimes, you may display specific error messages that are enough to trouble you in your work, and other times it may undergo some technical difficulty.
    Visit our site and get rid of your problem.

    ReplyDelete
  33. Integrated Assessment Services is a registered organization in Italy and group company of M/s. Integrated Assessment Services Pvt. Ltd. (IAS-INDIA). IAS has its direct presence in 6 countries and its associates in 14 more countries to deliver ISO certification, ISO training activities to its customers. Visit iso certification italy

    ReplyDelete
  34. You've come to the right place if you're having trouble logging in or signing in to the <a href="https://sites.google.com/wellsfargoo.xyz/wellsfargologinus/><b>Wells Fargo Login Account</b></a>. Get the quick and easy steps to access the Wells Fargo login account without any interruptions, and make sure you access the account in the correct manner as directed by the professional or support team.

    The Wells Fargo app is available for both Apple and Android devices. When you launch the app, you'll be prompted to log in. Simply enter your username and password in their respective entry spaces, just as you would on your desktop.

    Launch your web browser and navigate to your bank's website. Choose "online banking." Navigate to the homepage of your bank's website and click on the "online banking" link. If you don't see the words "online banking," look for the "login" button instead.

    To know more about <a href="https://sites.google.com/wellsfargoo.xyz/wellsfargologinus/><b>Wells Fargo Login</b></a>

    ReplyDelete
  35. You've come to the right place if you're having trouble logging in or signing in to the <a href="https://sites.google.com/wellsfargoo.xyz/wellsfargologinus/><b>Wells Fargo Login Account</b></a>. Get the quick and easy steps to access the Wells Fargo login account without any interruptions, and make sure you access the account in the correct manner as directed by the professional or support team.

    The Wells Fargo app is available for both Apple and Android devices. When you launch the app, you'll be prompted to log in. Simply enter your username and password in their respective entry spaces, just as you would on your desktop.

    Launch your web browser and navigate to your bank's website. Choose "online banking." Navigate to the homepage of your bank's website and click on the "online banking" link. If you don't see the words "online banking," look for the "login" button instead.

    ReplyDelete
  36. I seriously love your website.. Very nice colors & theme.
    Did you build this amazing site yourself? Please reply back as
    I’m planning to create my very own website and would like to learn where you got this
    from or exactly what the theme is called. Cheers! 경마사이트

    ReplyDelete
  37. Really a great addition, Thanks for sharing with us. This article will provide you complete information on the Venmo identity verification. Use the Venmo identity verification process and maintain the security of your Venmo account. If you plan on carrying and using a balance on Venmo, you'll have to verify your identity through the app.

    ReplyDelete
  38. Hi there, thank you for sharing such great piece of informative content with us. It is really amazing post it also helps me a lot.
    API Testing
    A* Search Algorithm
    uBlock Origin
    Google Forms Create Tutorial

    ReplyDelete
  39. This is a great post and enjoy the look of your blog very much. Thanks for sharing.
    파워볼

    ReplyDelete
  40. Amazing! Its really amazing article, I have got much clear idea regarding
    from this post. 파워볼 하는법

    ReplyDelete
  41. You need to take part in a contest for one of the best sites online. I’m going to highly recommend this web site! 온라인카지노

    ReplyDelete
  42. Onlookers Cheer as Trump's Atlantic City 스포츠중계 Demolished

    ReplyDelete
  43. Really liked your content. It is very appreciating you put effort you writing this content. Keep posting.

    ISO 9001 Certification
    ISO Certification Indonesia
    ISO Certification UK

    ReplyDelete
  44. unblocked games 6969
    Games to play unblocked are generally HTML5 and .io games. The term unblocked game is used to describe those types of games. Those are not blocked by college and school networks. These types of games can be played without any restriction. But colleges and organizations use firewalls to block games websites because students or executives focus on studies or jobs.

    ReplyDelete
  45. Are you more of a “fix it yourself” or “call an expert” kind of person? Masters Study

    ReplyDelete
  46. Those upsetting evaluations, for example, how to make scarcely enough, or essentially having a senseless complete to do, can set your assessments wild. In addition, in the event that you don't control those considerations, you after a short time end up perplexed to focus in on anything. Then strain sets in and turns your entire outing of control Buy Shatter Canada

    ReplyDelete