Search Results

Search found 658 results on 27 pages for 'carry all'.

Page 27/27 | < Previous Page | 23 24 25 26 27 

• Sniffing out SQL Code Smells: Inconsistent use of Symbolic names and Datatypes

  - by Phil Factor

  It is an awkward feeling. You’ve just delivered a database application that seems to be working fine in production, and you just run a few checks on it. You discover that there is a potential bug that, out of sheer good chance, hasn’t kicked in to produce an error; but it lurks, like a smoking bomb. Worse, maybe you find that the bug has started its evil work of corrupting the data, but in ways that nobody has, so far detected. You investigate, and find the damage. You are somehow going to have to repair it. Yes, it still very occasionally happens to me. It is not a nice feeling, and I do anything I can to prevent it happening. That’s why I’m interested in SQL code smells. SQL Code Smells aren’t necessarily bad practices, but just show you where to focus your attention when checking an application. Sometimes with databases the bugs can be subtle. SQL is rather like HTML: the language does its best to try to carry out your wishes, rather than to be picky about your bugs. Most of the time, this is a great benefit, but not always. One particular place where this can be detrimental is where you have implicit conversion between different data types. Most of the time it is completely harmless but we’re  concerned about the occasional time it isn’t. Let’s give an example: String truncation. Let’s give another even more frightening one, rounding errors on assignment to a number of different precision. Each requires a blog-post to explain in detail and I’m not now going to try. Just remember that it is not always a good idea to assign data to variables, parameters or even columns when they aren’t the same datatype, especially if you are relying on implicit conversion to work its magic.For details of the problem and the consequences, see here:  SR0014: Data loss might occur when casting from {Type1} to {Type2} . For any experienced Database Developer, this is a more frightening read than a Vampire Story. This is why one of the SQL Code Smells that makes me edgy, in my own or other peoples’ code, is to see parameters, variables and columns that have the same names and different datatypes. Whereas quite a lot of this is perfectly normal and natural, you need to check in case one of two things have gone wrong. Either sloppy naming, or mixed datatypes. Sure it is hard to remember whether you decided that the length of a log entry was 80 or 100 characters long, or the precision of a number. That is why a little check like this I’m going to show you is excellent for tidying up your code before you check it back into source Control! 1/ Checking Parameters only If you were just going to check parameters, you might just do this. It simply groups all the parameters, either input or output, of all the routines (e.g. stored procedures or functions) by their name and checks to see, in the HAVING clause, whether their data types are all the same. If not, it lists all the examples and their origin (the routine) Even this little check can occasionally be scarily revealing. ;WITH userParameter AS  ( SELECT   c.NAME AS ParameterName,  OBJECT_SCHEMA_NAME(c.object_ID) + '.' + OBJECT_NAME(c.object_ID) AS ObjectName,  t.name + ' '     + CASE     --we may have to put in the length            WHEN t.name IN ('char', 'varchar', 'nchar', 'nvarchar')             THEN '('               + CASE WHEN c.max_length = -1 THEN 'MAX'                ELSE CONVERT(VARCHAR(4),                    CASE WHEN t.name IN ('nchar', 'nvarchar')                      THEN c.max_length / 2 ELSE c.max_length                    END)                END + ')'         WHEN t.name IN ('decimal', 'numeric')             THEN '(' + CONVERT(VARCHAR(4), c.precision)                   + ',' + CONVERT(VARCHAR(4), c.Scale) + ')'         ELSE ''      END  --we've done with putting in the length      + CASE WHEN XML_collection_ID <> 0         THEN --deal with object schema names             '(' + CASE WHEN is_XML_Document = 1                    THEN 'DOCUMENT '                    ELSE 'CONTENT '                   END              + COALESCE(               (SELECT QUOTENAME(ss.name) + '.' + QUOTENAME(sc.name)                FROM sys.xml_schema_collections sc                INNER JOIN Sys.Schemas ss ON sc.schema_ID = ss.schema_ID                WHERE sc.xml_collection_ID = c.XML_collection_ID),'NULL') + ')'          ELSE ''         END        AS [DataType]  FROM sys.parameters c  INNER JOIN sys.types t ON c.user_Type_ID = t.user_Type_ID  WHERE OBJECT_SCHEMA_NAME(c.object_ID) <> 'sys'   AND parameter_id>0)SELECT CONVERT(CHAR(80),objectName+'.'+ParameterName),DataType FROM UserParameterWHERE ParameterName IN   (SELECT ParameterName FROM UserParameter    GROUP BY ParameterName    HAVING MIN(Datatype)<>MAX(DataType))ORDER BY ParameterName   so, in a very small example here, we have a @ClosingDelimiter variable that is only CHAR(1) when, by the looks of it, it should be up to ten characters long, or even worse, a function that should be a char(1) and seems to let in a string of ten characters. Worth investigating. Then we have a @Comment variable that can't decide whether it is a VARCHAR(2000) or a VARCHAR(MAX) 2/ Columns and Parameters Actually, once we’ve cleared up the mess we’ve made of our parameter-naming in the database we’re inspecting, we’re going to be more interested in listing both columns and parameters. We can do this by modifying the routine to list columns as well as parameters. Because of the slight complexity of creating the string version of the datatypes, we will create a fake table of both columns and parameters so that they can both be processed the same way. After all, we want the datatypes to match Unfortunately, parameters do not expose all the attributes we are interested in, such as whether they are nullable (oh yes, subtle bugs happen if this isn’t consistent for a datatype). We’ll have to leave them out for this check. Voila! A slight modification of the first routine ;WITH userObject AS  ( SELECT   Name AS DataName,--the actual name of the parameter or column ('@' removed)  --and the qualified object name of the routine  OBJECT_SCHEMA_NAME(ObjectID) + '.' + OBJECT_NAME(ObjectID) AS ObjectName,  --now the harder bit: the definition of the datatype.  TypeName + ' '     + CASE     --we may have to put in the length. e.g. CHAR (10)           WHEN TypeName IN ('char', 'varchar', 'nchar', 'nvarchar')             THEN '('               + CASE WHEN MaxLength = -1 THEN 'MAX'                ELSE CONVERT(VARCHAR(4),                    CASE WHEN TypeName IN ('nchar', 'nvarchar')                      THEN MaxLength / 2 ELSE MaxLength                    END)                END + ')'         WHEN TypeName IN ('decimal', 'numeric')--a BCD number!             THEN '(' + CONVERT(VARCHAR(4), Precision)                   + ',' + CONVERT(VARCHAR(4), Scale) + ')'         ELSE ''      END  --we've done with putting in the length      + CASE WHEN XML_collection_ID <> 0 --tush tush. XML         THEN --deal with object schema names             '(' + CASE WHEN is_XML_Document = 1                    THEN 'DOCUMENT '                    ELSE 'CONTENT '                   END              + COALESCE(               (SELECT TOP 1 QUOTENAME(ss.name) + '.' + QUOTENAME(sc.Name)                FROM sys.xml_schema_collections sc                INNER JOIN Sys.Schemas ss ON sc.schema_ID = ss.schema_ID                WHERE sc.xml_collection_ID = XML_collection_ID),'NULL') + ')'          ELSE ''         END        AS [DataType],       DataObjectType  FROM   (Select t.name AS TypeName, REPLACE(c.name,'@','') AS Name,          c.max_length AS MaxLength, c.precision AS [Precision],           c.scale AS [Scale], c.[Object_id] AS ObjectID, XML_collection_ID,          is_XML_Document,'P' AS DataobjectType  FROM sys.parameters c  INNER JOIN sys.types t ON c.user_Type_ID = t.user_Type_ID  AND parameter_id>0  UNION all  Select t.name AS TypeName, c.name AS Name, c.max_length AS MaxLength,          c.precision AS [Precision], c.scale AS [Scale],          c.[Object_id] AS ObjectID, XML_collection_ID,is_XML_Document,          'C' AS DataobjectType            FROM sys.columns c  INNER JOIN sys.types t ON c.user_Type_ID = t.user_Type_ID   WHERE OBJECT_SCHEMA_NAME(c.object_ID) <> 'sys'  )f)SELECT CONVERT(CHAR(80),objectName+'.'   + CASE WHEN DataobjectType ='P' THEN '@' ELSE '' END + DataName),DataType FROM UserObjectWHERE DataName IN   (SELECT DataName FROM UserObject   GROUP BY DataName    HAVING MIN(Datatype)<>MAX(DataType))ORDER BY DataName     Hmm. I can tell you I found quite a few minor issues with the various tabases I tested this on, and found some potential bugs that really leap out at you from the results. Here is the start of the result for AdventureWorks. Yes, AccountNumber is, for some reason, a Varchar(10) in the Customer table. Hmm. odd. Why is a city fifty characters long in that view?  The idea of the description of a colour being 256 characters long seems over-ambitious. Go down the list and you'll spot other mistakes. There are no bugs, but just mess. We started out with a listing to examine parameters, then we mixed parameters and columns. Our last listing is for a slightly more in-depth look at table columns. You’ll notice that we’ve delibarately removed the indication of whether a column is persisted, or is an identity column because that gives us false positives for our code smells. If you just want to browse your metadata for other reasons (and it can quite help in some circumstances) then uncomment them! ;WITH userColumns AS  ( SELECT   c.NAME AS columnName,  OBJECT_SCHEMA_NAME(c.object_ID) + '.' + OBJECT_NAME(c.object_ID) AS ObjectName,  REPLACE(t.name + ' '   + CASE WHEN is_computed = 1 THEN ' AS ' + --do DDL for a computed column          (SELECT definition FROM sys.computed_columns cc           WHERE cc.object_id = c.object_id AND cc.column_ID = c.column_ID)     --we may have to put in the length            WHEN t.Name IN ('char', 'varchar', 'nchar', 'nvarchar')             THEN '('               + CASE WHEN c.Max_Length = -1 THEN 'MAX'                ELSE CONVERT(VARCHAR(4),                    CASE WHEN t.Name IN ('nchar', 'nvarchar')                      THEN c.Max_Length / 2 ELSE c.Max_Length                    END)                END + ')'       WHEN t.name IN ('decimal', 'numeric')       THEN '(' + CONVERT(VARCHAR(4), c.precision) + ',' + CONVERT(VARCHAR(4), c.Scale) + ')'       ELSE ''      END + CASE WHEN c.is_rowguidcol = 1          THEN ' ROWGUIDCOL'          ELSE ''         END + CASE WHEN XML_collection_ID <> 0            THEN --deal with object schema names             '(' + CASE WHEN is_XML_Document = 1                THEN 'DOCUMENT '                ELSE 'CONTENT '               END + COALESCE((SELECT                QUOTENAME(ss.name) + '.' + QUOTENAME(sc.name)                FROM                sys.xml_schema_collections sc                INNER JOIN Sys.Schemas ss ON sc.schema_ID = ss.schema_ID                WHERE                sc.xml_collection_ID = c.XML_collection_ID),                'NULL') + ')'            ELSE ''           END + CASE WHEN is_identity = 1             THEN CASE WHEN OBJECTPROPERTY(object_id,                'IsUserTable') = 1 AND COLUMNPROPERTY(object_id,                c.name,                'IsIDNotForRepl') = 0 AND OBJECTPROPERTY(object_id,                'IsMSShipped') = 0                THEN ''                ELSE ' NOT FOR REPLICATION '               END             ELSE ''            END + CASE WHEN c.is_nullable = 0               THEN ' NOT NULL'               ELSE ' NULL'              END + CASE                WHEN c.default_object_id <> 0                THEN ' DEFAULT ' + object_Definition(c.default_object_id)                ELSE ''               END + CASE                WHEN c.collation_name IS NULL                THEN ''                WHEN c.collation_name <> (SELECT                collation_name                FROM                sys.databases                WHERE                name = DB_NAME()) COLLATE Latin1_General_CI_AS                THEN COALESCE(' COLLATE ' + c.collation_name,                '')                ELSE ''                END,'  ',' ') AS [DataType]FROM sys.columns c  INNER JOIN sys.types t ON c.user_Type_ID = t.user_Type_ID  WHERE OBJECT_SCHEMA_NAME(c.object_ID) <> 'sys')SELECT CONVERT(CHAR(80),objectName+'.'+columnName),DataType FROM UserColumnsWHERE columnName IN (SELECT columnName FROM UserColumns  GROUP BY columnName  HAVING MIN(Datatype)<>MAX(DataType))ORDER BY columnName If you take a look down the results against Adventureworks, you'll see once again that there are things to investigate, mostly, in the illustration, discrepancies between null and non-null datatypes So I here you ask, what about temporary variables within routines? If ever there was a source of elusive bugs, you'll find it there. Sadly, these temporary variables are not stored in the metadata so we'll have to find a more subtle way of flushing these out, and that will, I'm afraid, have to wait!

  Read the article

• Informed TDD &ndash; Kata &ldquo;To Roman Numerals&rdquo;

  - by Ralf Westphal

  Originally posted on: http://geekswithblogs.net/theArchitectsNapkin/archive/2014/05/28/informed-tdd-ndash-kata-ldquoto-roman-numeralsrdquo.aspxIn a comment on my article on what I call Informed TDD (ITDD) reader gustav asked how this approach would apply to the kata “To Roman Numerals”. And whether ITDD wasn´t a violation of TDD´s principle of leaving out “advanced topics like mocks”. I like to respond with this article to his questions. There´s more to say than fits into a commentary. Mocks and TDD I don´t see in how far TDD is avoiding or opposed to mocks. TDD and mocks are orthogonal. TDD is about pocess, mocks are about structure and costs. Maybe by moving forward in tiny red+green+refactor steps less need arises for mocks. But then… if the functionality you need to implement requires “expensive” resource access you can´t avoid using mocks. Because you don´t want to constantly run all your tests against the real resource. True, in ITDD mocks seem to be in almost inflationary use. That´s not what you usually see in TDD demonstrations. However, there´s a reason for that as I tried to explain. I don´t use mocks as proxies for “expensive” resource. Rather they are stand-ins for functionality not yet implemented. They allow me to get a test green on a high level of abstraction. That way I can move forward in a top-down fashion. But if you think of mocks as “advanced” or if you don´t want to use a tool like JustMock, then you don´t need to use mocks. You just need to stand the sight of red tests for a little longer ;-) Let me show you what I mean by that by doing a kata. ITDD for “To Roman Numerals” gustav asked for the kata “To Roman Numerals”. I won´t explain the requirements again. You can find descriptions and TDD demonstrations all over the internet, like this one from Corey Haines. Now here is, how I would do this kata differently. 1. Analyse A demonstration of TDD should never skip the analysis phase. It should be made explicit. The requirements should be formalized and acceptance test cases should be compiled. “Formalization” in this case to me means describing the API of the required functionality. “[D]esign a program to work with Roman numerals” like written in this “requirement document” is not enough to start software development. Coding should only begin, if the interface between the “system under development” and its context is clear. If this interface is not readily recognizable from the requirements, it has to be developed first. Exploration of interface alternatives might be in order. It might be necessary to show several interface mock-ups to the customer – even if that´s you fellow developer. Designing the interface is a task of it´s own. It should not be mixed with implementing the required functionality behind the interface. Unfortunately, though, this happens quite often in TDD demonstrations. TDD is used to explore the API and implement it at the same time. To me that´s a violation of the Single Responsibility Principle (SRP) which not only should hold for software functional units but also for tasks or activities. In the case of this kata the API fortunately is obvious. Just one function is needed: string ToRoman(int arabic). And it lives in a class ArabicRomanConversions. Now what about acceptance test cases? There are hardly any stated in the kata descriptions. Roman numerals are explained, but no specific test cases from the point of view of a customer. So I just “invent” some acceptance test cases by picking roman numerals from a wikipedia article. They are supposed to be just “typical examples” without special meaning. Given the acceptance test cases I then try to develop an understanding of the problem domain. I´ll spare you that. The domain is trivial and is explain in almost all kata descriptions. How roman numerals are built is not difficult to understand. What´s more difficult, though, might be to find an efficient solution to convert into them automatically. 2. Solve The usual TDD demonstration skips a solution finding phase. Like the interface exploration it´s mixed in with the implementation. But I don´t think this is how it should be done. I even think this is not how it really works for the people demonstrating TDD. They´re simplifying their true software development process because they want to show a streamlined TDD process. I doubt this is helping anybody. Before you code you better have a plan what to code. This does not mean you have to do “Big Design Up-Front”. It just means: Have a clear picture of the logical solution in your head before you start to build a physical solution (code). Evidently such a solution can only be as good as your understanding of the problem. If that´s limited your solution will be limited, too. Fortunately, in the case of this kata your understanding does not need to be limited. Thus the logical solution does not need to be limited or preliminary or tentative. That does not mean you need to know every line of code in advance. It just means you know the rough structure of your implementation beforehand. Because it should mirror the process described by the logical or conceptual solution. Here´s my solution approach: The arabic “encoding” of numbers represents them as an ordered set of powers of 10. Each digit is a factor to multiply a power of ten with. The “encoding” 123 is the short form for a set like this: {1*10^2, 2*10^1, 3*10^0}. And the number is the sum of the set members. The roman “encoding” is different. There is no base (like 10 for arabic numbers), there are just digits of different value, and they have to be written in descending order. The “encoding” XVI is short for [10, 5, 1]. And the number is still the sum of the members of this list. The roman “encoding” thus is simpler than the arabic. Each “digit” can be taken at face value. No multiplication with a base required. But what about IV which looks like a contradiction to the above rule? It is not – if you accept roman “digits” not to be limited to be single characters only. Usually I, V, X, L, C, D, M are viewed as “digits”, and IV, IX etc. are viewed as nuisances preventing a simple solution. All looks different, though, once IV, IX etc. are taken as “digits”. Then MCMLIV is just a sum: M+CM+L+IV which is 1000+900+50+4. Whereas before it would have been understood as M-C+M+L-I+V – which is more difficult because here some “digits” get subtracted. Here´s the list of roman “digits” with their values: {1, I}, {4, IV}, {5, V}, {9, IX}, {10, X}, {40, XL}, {50, L}, {90, XC}, {100, C}, {400, CD}, {500, D}, {900, CM}, {1000, M} Since I take IV, IX etc. as “digits” translating an arabic number becomes trivial. I just need to find the values of the roman “digits” making up the number, e.g. 1954 is made up of 1000, 900, 50, and 4. I call those “digits” factors. If I move from the highest factor (M=1000) to the lowest (I=1) then translation is a two phase process: Find all the factors Translate the factors found Compile the roman representation Translation is just a look-up. Finding, though, needs some calculation: Find the highest remaining factor fitting in the value Remember and subtract it from the value Repeat with remaining value and remaining factors Please note: This is just an algorithm. It´s not code, even though it might be close. Being so close to code in my solution approach is due to the triviality of the problem. In more realistic examples the conceptual solution would be on a higher level of abstraction. With this solution in hand I finally can do what TDD advocates: find and prioritize test cases. As I can see from the small process description above, there are two aspects to test: Test the translation Test the compilation Test finding the factors Testing the translation primarily means to check if the map of factors and digits is comprehensive. That´s simple, even though it might be tedious. Testing the compilation is trivial. Testing factor finding, though, is a tad more complicated. I can think of several steps: First check, if an arabic number equal to a factor is processed correctly (e.g. 1000=M). Then check if an arabic number consisting of two consecutive factors (e.g. 1900=[M,CM]) is processed correctly. Then check, if a number consisting of the same factor twice is processed correctly (e.g. 2000=[M,M]). Finally check, if an arabic number consisting of non-consecutive factors (e.g. 1400=[M,CD]) is processed correctly. I feel I can start an implementation now. If something becomes more complicated than expected I can slow down and repeat this process. 3. Implement First I write a test for the acceptance test cases. It´s red because there´s no implementation even of the API. That´s in conformance with “TDD lore”, I´d say: Next I implement the API: The acceptance test now is formally correct, but still red of course. This will not change even now that I zoom in. Because my goal is not to most quickly satisfy these tests, but to implement my solution in a stepwise manner. That I do by “faking” it: I just “assume” three functions to represent the transformation process of my solution: My hypothesis is that those three functions in conjunction produce correct results on the API-level. I just have to implement them correctly. That´s what I´m trying now – one by one. I start with a simple “detail function”: Translate(). And I start with all the test cases in the obvious equivalence partition: As you can see I dare to test a private method. Yes. That´s a white box test. But as you´ll see it won´t make my tests brittle. It serves a purpose right here and now: it lets me focus on getting one aspect of my solution right. Here´s the implementation to satisfy the test: It´s as simple as possible. Right how TDD wants me to do it: KISS. Now for the second equivalence partition: translating multiple factors. (It´a pattern: if you need to do something repeatedly separate the tests for doing it once and doing it multiple times.) In this partition I just need a single test case, I guess. Stepping up from a single translation to multiple translations is no rocket science: Usually I would have implemented the final code right away. Splitting it in two steps is just for “educational purposes” here. How small your implementation steps are is a matter of your programming competency. Some “see” the final code right away before their mental eye – others need to work their way towards it. Having two tests I find more important. Now for the next low hanging fruit: compilation. It´s even simpler than translation. A single test is enough, I guess. And normally I would not even have bothered to write that one, because the implementation is so simple. I don´t need to test .NET framework functionality. But again: if it serves the educational purpose… Finally the most complicated part of the solution: finding the factors. There are several equivalence partitions. But still I decide to write just a single test, since the structure of the test data is the same for all partitions: Again, I´m faking the implementation first: I focus on just the first test case. No looping yet. Faking lets me stay on a high level of abstraction. I can write down the implementation of the solution without bothering myself with details of how to actually accomplish the feat. That´s left for a drill down with a test of the fake function: There are two main equivalence partitions, I guess: either the first factor is appropriate or some next. The implementation seems easy. Both test cases are green. (Of course this only works on the premise that there´s always a matching factor. Which is the case since the smallest factor is 1.) And the first of the equivalence partitions on the higher level also is satisfied: Great, I can move on. Now for more than a single factor: Interestingly not just one test becomes green now, but all of them. Great! You might say, then I must have done not the simplest thing possible. And I would reply: I don´t care. I did the most obvious thing. But I also find this loop very simple. Even simpler than a recursion of which I had thought briefly during the problem solving phase. And by the way: Also the acceptance tests went green: Mission accomplished. At least functionality wise. Now I´ve to tidy up things a bit. TDD calls for refactoring. Not uch refactoring is needed, because I wrote the code in top-down fashion. I faked it until I made it. I endured red tests on higher levels while lower levels weren´t perfected yet. But this way I saved myself from refactoring tediousness. At the end, though, some refactoring is required. But maybe in a different way than you would expect. That´s why I rather call it “cleanup”. First I remove duplication. There are two places where factors are defined: in Translate() and in Find_factors(). So I factor the map out into a class constant. Which leads to a small conversion in Find_factors(): And now for the big cleanup: I remove all tests of private methods. They are scaffolding tests to me. They only have temporary value. They are brittle. Only acceptance tests need to remain. However, I carry over the single “digit” tests from Translate() to the acceptance test. I find them valuable to keep, since the other acceptance tests only exercise a subset of all roman “digits”. This then is my final test class: And this is the final production code: Test coverage as reported by NCrunch is 100%: Reflexion Is this the smallest possible code base for this kata? Sure not. You´ll find more concise solutions on the internet. But LOC are of relatively little concern – as long as I can understand the code quickly. So called “elegant” code, however, often is not easy to understand. The same goes for KISS code – especially if left unrefactored, as it is often the case. That´s why I progressed from requirements to final code the way I did. I first understood and solved the problem on a conceptual level. Then I implemented it top down according to my design. I also could have implemented it bottom-up, since I knew some bottom of the solution. That´s the leaves of the functional decomposition tree. Where things became fuzzy, since the design did not cover any more details as with Find_factors(), I repeated the process in the small, so to speak: fake some top level, endure red high level tests, while first solving a simpler problem. Using scaffolding tests (to be thrown away at the end) brought two advantages: Encapsulation of the implementation details was not compromised. Naturally private methods could stay private. I did not need to make them internal or public just to be able to test them. I was able to write focused tests for small aspects of the solution. No need to test everything through the solution root, the API. The bottom line thus for me is: Informed TDD produces cleaner code in a systematic way. It conforms to core principles of programming: Single Responsibility Principle and/or Separation of Concerns. Distinct roles in development – being a researcher, being an engineer, being a craftsman – are represented as different phases. First find what, what there is. Then devise a solution. Then code the solution, manifest the solution in code. Writing tests first is a good practice. But it should not be taken dogmatic. And above all it should not be overloaded with purposes. And finally: moving from top to bottom through a design produces refactored code right away. Clean code thus almost is inevitable – and not left to a refactoring step at the end which is skipped often for different reasons.   PS: Yes, I have done this kata several times. But that has only an impact on the time needed for phases 1 and 2. I won´t skip them because of that. And there are no shortcuts during implementation because of that.

  Read the article

• Understanding Request Validation in ASP.NET MVC 3

  - by imran_ku07

       Introduction:             A fact that you must always remember "never ever trust user inputs". An application that trusts user inputs may be easily vulnerable to XSS, XSRF, SQL Injection, etc attacks. XSS and XSRF are very dangerous attacks. So to mitigate these attacks ASP.NET introduced request validation in ASP.NET 1.1. During request validation, ASP.NET will throw HttpRequestValidationException: 'A potentially dangerous XXX value was detected from the client', if he found, < followed by an exclamation(like <!) or < followed by the letters a through z(like <s) or & followed by a pound sign(like &#123) as a part of query string, posted form and cookie collection. In ASP.NET 4.0, request validation becomes extensible. This means that you can extend request validation. Also in ASP.NET 4.0, by default request validation is enabled before the BeginRequest phase of an HTTP request. ASP.NET MVC 3 moves one step further by making request validation granular. This allows you to disable request validation for some properties of a model while maintaining request validation for all other cases. In this article I will show you the use of request validation in ASP.NET MVC 3. Then I will briefly explain the internal working of granular request validation.       Description:             First of all create a new ASP.NET MVC 3 application. Then create a simple model class called MyModel,     public class MyModel { public string Prop1 { get; set; } public string Prop2 { get; set; } }             Then just update the index action method as follows,   public ActionResult Index(MyModel p) { return View(); }             Now just run this application. You will find that everything works just fine. Now just append this query string ?Prop1=<s to the url of this application, you will get the HttpRequestValidationException exception.           Now just decorate the Index action method with [ValidateInputAttribute(false)],   [ValidateInput(false)] public ActionResult Index(MyModel p) { return View(); }             Run this application again with same query string. You will find that your application run without any unhandled exception.           Up to now, there is nothing new in ASP.NET MVC 3 because ValidateInputAttribute was present in the previous versions of ASP.NET MVC. Any problem with this approach? Yes there is a problem with this approach. The problem is that now users can send html for both Prop1 and Prop2 properties and a lot of developers are not aware of it. This means that now everyone can send html with both parameters(e.g, ?Prop1=<s&Prop2=<s). So ValidateInput attribute does not gives you the guarantee that your application is safe to XSS or XSRF. This is the reason why ASP.NET MVC team introduced granular request validation in ASP.NET MVC 3. Let's see this feature.           Remove [ValidateInputAttribute(false)] on Index action and update MyModel class as follows,   public class MyModel { [AllowHtml] public string Prop1 { get; set; } public string Prop2 { get; set; } }             Note that AllowHtml attribute is only decorated on Prop1 property. Run this application again with ?Prop1=<s query string. You will find that your application run just fine. Run this application again with ?Prop1=<s&Prop2=<s query string, you will get HttpRequestValidationException exception. This shows that the granular request validation in ASP.NET MVC 3 only allows users to send html for properties decorated with AllowHtml attribute.            Sometimes you may need to access Request.QueryString or Request.Form directly. You may change your code as follows,   [ValidateInput(false)] public ActionResult Index() { var prop1 = Request.QueryString["Prop1"]; return View(); }             Run this application again, you will get the HttpRequestValidationException exception again even you have [ValidateInput(false)] on your Index action. The reason is that Request flags are still not set to unvalidate. I will explain this later. For making this work you need to use Unvalidated extension method,     public ActionResult Index() { var q = Request.Unvalidated().QueryString; var prop1 = q["Prop1"]; return View(); }             Unvalidated extension method is defined in System.Web.Helpers namespace . So you need to add using System.Web.Helpers; in this class file. Run this application again, your application run just fine.             There you have it. If you are not curious to know the internal working of granular request validation then you can skip next paragraphs completely. If you are interested then carry on reading.             Create a new ASP.NET MVC 2 application, then open global.asax.cs file and the following lines,     protected void Application_BeginRequest() { var q = Request.QueryString; }             Then make the Index action method as,    [ValidateInput(false)] public ActionResult Index(string id) { return View(); }             Please note that the Index action method contains a parameter and this action method is decorated with [ValidateInput(false)]. Run this application again, but now with ?id=<s query string, you will get HttpRequestValidationException exception at Application_BeginRequest method. Now just add the following entry in web.config,   <httpRuntime requestValidationMode="2.0"/>             Now run this application again. This time your application will run just fine. Now just see the following quote from ASP.NET 4 Breaking Changes,   In ASP.NET 4, by default, request validation is enabled for all requests, because it is enabled before the BeginRequest phase of an HTTP request. As a result, request validation applies to requests for all ASP.NET resources, not just .aspx page requests. This includes requests such as Web service calls and custom HTTP handlers. Request validation is also active when custom HTTP modules are reading the contents of an HTTP request.             This clearly state that request validation is enabled before the BeginRequest phase of an HTTP request. For understanding what does enabled means here, we need to see HttpRequest.ValidateInput, HttpRequest.QueryString and HttpRequest.Form methods/properties in System.Web assembly. Here is the implementation of HttpRequest.ValidateInput, HttpRequest.QueryString and HttpRequest.Form methods/properties in System.Web assembly,     public NameValueCollection Form { get { if (this._form == null) { this._form = new HttpValueCollection(); if (this._wr != null) { this.FillInFormCollection(); } this._form.MakeReadOnly(); } if (this._flags[2]) { this._flags.Clear(2); this.ValidateNameValueCollection(this._form, RequestValidationSource.Form); } return this._form; } } public NameValueCollection QueryString { get { if (this._queryString == null) { this._queryString = new HttpValueCollection(); if (this._wr != null) { this.FillInQueryStringCollection(); } this._queryString.MakeReadOnly(); } if (this._flags[1]) { this._flags.Clear(1); this.ValidateNameValueCollection(this._queryString, RequestValidationSource.QueryString); } return this._queryString; } } public void ValidateInput() { if (!this._flags[0x8000]) { this._flags.Set(0x8000); this._flags.Set(1); this._flags.Set(2); this._flags.Set(4); this._flags.Set(0x40); this._flags.Set(0x80); this._flags.Set(0x100); this._flags.Set(0x200); this._flags.Set(8); } }             The above code indicates that HttpRequest.QueryString and HttpRequest.Form will only validate the querystring and form collection if certain flags are set. These flags are automatically set if you call HttpRequest.ValidateInput method. Now run the above application again(don't forget to append ?id=<s query string in the url) with the same settings(i.e, requestValidationMode="2.0" setting in web.config and Application_BeginRequest method in global.asax.cs), your application will run just fine. Now just update the Application_BeginRequest method as,   protected void Application_BeginRequest() { Request.ValidateInput(); var q = Request.QueryString; }             Note that I am calling Request.ValidateInput method prior to use Request.QueryString property. ValidateInput method will internally set certain flags(discussed above). These flags will then tells the Request.QueryString (and Request.Form) property that validate the query string(or form) when user call Request.QueryString(or Request.Form) property. So running this application again with ?id=<s query string will throw HttpRequestValidationException exception. Now I hope it is clear to you that what does requestValidationMode do. It just tells the ASP.NET that not invoke the Request.ValidateInput method internally before the BeginRequest phase of an HTTP request if requestValidationMode is set to a value less than 4.0 in web.config. Here is the implementation of HttpRequest.ValidateInputIfRequiredByConfig method which will prove this statement(Don't be confused with HttpRequest and Request. Request is the property of HttpRequest class),    internal void ValidateInputIfRequiredByConfig() { ............................................................... ............................................................... ............................................................... ............................................................... if (httpRuntime.RequestValidationMode >= VersionUtil.Framework40) { this.ValidateInput(); } }              Hopefully the above discussion will clear you how requestValidationMode works in ASP.NET 4. It is also interesting to note that both HttpRequest.QueryString and HttpRequest.Form only throws the exception when you access them first time. Any subsequent access to HttpRequest.QueryString and HttpRequest.Form will not throw any exception. Continuing with the above example, just update Application_BeginRequest method in global.asax.cs file as,   protected void Application_BeginRequest() { try { var q = Request.QueryString; var f = Request.Form; } catch//swallow this exception { } var q1 = Request.QueryString; var f1 = Request.Form; }             Without setting requestValidationMode to 2.0 and without decorating ValidateInput attribute on Index action, your application will work just fine because both HttpRequest.QueryString and HttpRequest.Form will clear their flags after reading HttpRequest.QueryString and HttpRequest.Form for the first time(see the implementation of HttpRequest.QueryString and HttpRequest.Form above).           Now let's see ASP.NET MVC 3 granular request validation internal working. First of all we need to see type of HttpRequest.QueryString and HttpRequest.Form properties. Both HttpRequest.QueryString and HttpRequest.Form properties are of type NameValueCollection which is inherited from the NameObjectCollectionBase class. NameObjectCollectionBase class contains _entriesArray, _entriesTable, NameObjectEntry.Key and NameObjectEntry.Value fields which granular request validation uses internally. In addition granular request validation also uses _queryString, _form and _flags fields, ValidateString method and the Indexer of HttpRequest class. Let's see when and how granular request validation uses these fields.           Create a new ASP.NET MVC 3 application. Then put a breakpoint at Application_BeginRequest method and another breakpoint at HomeController.Index method. Now just run this application. When the break point inside Application_BeginRequest method hits then add the following expression in quick watch window, System.Web.HttpContext.Current.Request.QueryString. You will see the following screen,                                              Now Press F5 so that the second breakpoint inside HomeController.Index method hits. When the second breakpoint hits then add the following expression in quick watch window again, System.Web.HttpContext.Current.Request.QueryString. You will see the following screen,                            First screen shows that _entriesTable field is of type System.Collections.Hashtable and _entriesArray field is of type System.Collections.ArrayList during the BeginRequest phase of the HTTP request. While the second screen shows that _entriesTable type is changed to Microsoft.Web.Infrastructure.DynamicValidationHelper.LazilyValidatingHashtable and _entriesArray type is changed to Microsoft.Web.Infrastructure.DynamicValidationHelper.LazilyValidatingArrayList during executing the Index action method. In addition to these members, ASP.NET MVC 3 also perform some operation on _flags, _form, _queryString and other members of HttpRuntime class internally. This shows that ASP.NET MVC 3 performing some operation on the members of HttpRequest class for making granular request validation possible.           Both LazilyValidatingArrayList and LazilyValidatingHashtable classes are defined in the Microsoft.Web.Infrastructure assembly. You may wonder why their name starts with Lazily. The fact is that now with ASP.NET MVC 3, request validation will be performed lazily. In simple words, Microsoft.Web.Infrastructure assembly is now taking the responsibility for request validation from System.Web assembly. See the below screens. The first screen depicting HttpRequestValidationException exception in ASP.NET MVC 2 application while the second screen showing HttpRequestValidationException exception in ASP.NET MVC 3 application.   In MVC 2:                 In MVC 3:                          The stack trace of the second screenshot shows that Microsoft.Web.Infrastructure assembly (instead of System.Web assembly) is now performing request validation in ASP.NET MVC 3. Now you may ask: where Microsoft.Web.Infrastructure assembly is performing some operation on the members of HttpRequest class. There are at least two places where the Microsoft.Web.Infrastructure assembly performing some operation , Microsoft.Web.Infrastructure.DynamicValidationHelper.GranularValidationReflectionUtil.GetInstance method and Microsoft.Web.Infrastructure.DynamicValidationHelper.ValidationUtility.CollectionReplacer.ReplaceCollection method, Here is the implementation of these methods,   private static GranularValidationReflectionUtil GetInstance() { try { if (DynamicValidationShimReflectionUtil.Instance != null) { return null; } GranularValidationReflectionUtil util = new GranularValidationReflectionUtil(); Type containingType = typeof(NameObjectCollectionBase); string fieldName = "_entriesArray"; bool isStatic = false; Type fieldType = typeof(ArrayList); FieldInfo fieldInfo = CommonReflectionUtil.FindField(containingType, fieldName, isStatic, fieldType); util._del_get_NameObjectCollectionBase_entriesArray = MakeFieldGetterFunc<NameObjectCollectionBase, ArrayList>(fieldInfo); util._del_set_NameObjectCollectionBase_entriesArray = MakeFieldSetterFunc<NameObjectCollectionBase, ArrayList>(fieldInfo); Type type6 = typeof(NameObjectCollectionBase); string str2 = "_entriesTable"; bool flag2 = false; Type type7 = typeof(Hashtable); FieldInfo info2 = CommonReflectionUtil.FindField(type6, str2, flag2, type7); util._del_get_NameObjectCollectionBase_entriesTable = MakeFieldGetterFunc<NameObjectCollectionBase, Hashtable>(info2); util._del_set_NameObjectCollectionBase_entriesTable = MakeFieldSetterFunc<NameObjectCollectionBase, Hashtable>(info2); Type targetType = CommonAssemblies.System.GetType("System.Collections.Specialized.NameObjectCollectionBase+NameObjectEntry"); Type type8 = targetType; string str3 = "Key"; bool flag3 = false; Type type9 = typeof(string); FieldInfo info3 = CommonReflectionUtil.FindField(type8, str3, flag3, type9); util._del_get_NameObjectEntry_Key = MakeFieldGetterFunc<string>(targetType, info3); Type type10 = targetType; string str4 = "Value"; bool flag4 = false; Type type11 = typeof(object); FieldInfo info4 = CommonReflectionUtil.FindField(type10, str4, flag4, type11); util._del_get_NameObjectEntry_Value = MakeFieldGetterFunc<object>(targetType, info4); util._del_set_NameObjectEntry_Value = MakeFieldSetterFunc(targetType, info4); Type type12 = typeof(HttpRequest); string methodName = "ValidateString"; bool flag5 = false; Type[] argumentTypes = new Type[] { typeof(string), typeof(string), typeof(RequestValidationSource) }; Type returnType = typeof(void); MethodInfo methodInfo = CommonReflectionUtil.FindMethod(type12, methodName, flag5, argumentTypes, returnType); util._del_validateStringCallback = CommonReflectionUtil.MakeFastCreateDelegate<HttpRequest, ValidateStringCallback>(methodInfo); Type type = CommonAssemblies.SystemWeb.GetType("System.Web.HttpValueCollection"); util._del_HttpValueCollection_ctor = CommonReflectionUtil.MakeFastNewObject<Func<NameValueCollection>>(type); Type type14 = typeof(HttpRequest); string str6 = "_form"; bool flag6 = false; Type type15 = type; FieldInfo info6 = CommonReflectionUtil.FindField(type14, str6, flag6, type15); util._del_get_HttpRequest_form = MakeFieldGetterFunc<HttpRequest, NameValueCollection>(info6); util._del_set_HttpRequest_form = MakeFieldSetterFunc(typeof(HttpRequest), info6); Type type16 = typeof(HttpRequest); string str7 = "_queryString"; bool flag7 = false; Type type17 = type; FieldInfo info7 = CommonReflectionUtil.FindField(type16, str7, flag7, type17); util._del_get_HttpRequest_queryString = MakeFieldGetterFunc<HttpRequest, NameValueCollection>(info7); util._del_set_HttpRequest_queryString = MakeFieldSetterFunc(typeof(HttpRequest), info7); Type type3 = CommonAssemblies.SystemWeb.GetType("System.Web.Util.SimpleBitVector32"); Type type18 = typeof(HttpRequest); string str8 = "_flags"; bool flag8 = false; Type type19 = type3; FieldInfo flagsFieldInfo = CommonReflectionUtil.FindField(type18, str8, flag8, type19); Type type20 = type3; string str9 = "get_Item"; bool flag9 = false; Type[] typeArray4 = new Type[] { typeof(int) }; Type type21 = typeof(bool); MethodInfo itemGetter = CommonReflectionUtil.FindMethod(type20, str9, flag9, typeArray4, type21); Type type22 = type3; string str10 = "set_Item"; bool flag10 = false; Type[] typeArray6 = new Type[] { typeof(int), typeof(bool) }; Type type23 = typeof(void); MethodInfo itemSetter = CommonReflectionUtil.FindMethod(type22, str10, flag10, typeArray6, type23); MakeRequestValidationFlagsAccessors(flagsFieldInfo, itemGetter, itemSetter, out util._del_BitVector32_get_Item, out util._del_BitVector32_set_Item); return util; } catch { return null; } } private static void ReplaceCollection(HttpContext context, FieldAccessor<NameValueCollection> fieldAccessor, Func<NameValueCollection> propertyAccessor, Action<NameValueCollection> storeInUnvalidatedCollection, RequestValidationSource validationSource, ValidationSourceFlag validationSourceFlag) { NameValueCollection originalBackingCollection; ValidateStringCallback validateString; SimpleValidateStringCallback simpleValidateString; Func<NameValueCollection> getActualCollection; Action<NameValueCollection> makeCollectionLazy; HttpRequest request = context.Request; Func<bool> getValidationFlag = delegate { return _reflectionUtil.GetRequestValidationFlag(request, validationSourceFlag); }; Func<bool> func = delegate { return !getValidationFlag(); }; Action<bool> setValidationFlag = delegate (bool value) { _reflectionUtil.SetRequestValidationFlag(request, validationSourceFlag, value); }; if ((fieldAccessor.Value != null) && func()) { storeInUnvalidatedCollection(fieldAccessor.Value); } else { originalBackingCollection = fieldAccessor.Value; validateString = _reflectionUtil.MakeValidateStringCallback(context.Request); simpleValidateString = delegate (string value, string key) { if (((key == null) || !key.StartsWith("__", StringComparison.Ordinal)) && !string.IsNullOrEmpty(value)) { validateString(value, key, validationSource); } }; getActualCollection = delegate { fieldAccessor.Value = originalBackingCollection; bool flag = getValidationFlag(); setValidationFlag(false); NameValueCollection col = propertyAccessor(); setValidationFlag(flag); storeInUnvalidatedCollection(new NameValueCollection(col)); return col; }; makeCollectionLazy = delegate (NameValueCollection col) { simpleValidateString(col[null], null); LazilyValidatingArrayList array = new LazilyValidatingArrayList(_reflectionUtil.GetNameObjectCollectionEntriesArray(col), simpleValidateString); _reflectionUtil.SetNameObjectCollectionEntriesArray(col, array); LazilyValidatingHashtable table = new LazilyValidatingHashtable(_reflectionUtil.GetNameObjectCollectionEntriesTable(col), simpleValidateString); _reflectionUtil.SetNameObjectCollectionEntriesTable(col, table); }; Func<bool> hasValidationFired = func; Action disableValidation = delegate { setValidationFlag(false); }; Func<int> fillInActualFormContents = delegate { NameValueCollection values = getActualCollection(); makeCollectionLazy(values); return values.Count; }; DeferredCountArrayList list = new DeferredCountArrayList(hasValidationFired, disableValidation, fillInActualFormContents); NameValueCollection target = _reflectionUtil.NewHttpValueCollection(); _reflectionUtil.SetNameObjectCollectionEntriesArray(target, list); fieldAccessor.Value = target; } }             Hopefully the above code will help you to understand the internal working of granular request validation. It is also important to note that Microsoft.Web.Infrastructure assembly invokes HttpRequest.ValidateInput method internally. For further understanding please see Microsoft.Web.Infrastructure assembly code. Finally you may ask: at which stage ASP NET MVC 3 will invoke these methods. You will find this answer by looking at the following method source,   Unvalidated extension method for HttpRequest class defined in System.Web.Helpers.Validation class. System.Web.Mvc.MvcHandler.ProcessRequestInit method. System.Web.Mvc.ControllerActionInvoker.ValidateRequest method. System.Web.WebPages.WebPageHttpHandler.ProcessRequestInternal method.       Summary:             ASP.NET helps in preventing XSS attack using a feature called request validation. In this article, I showed you how you can use granular request validation in ASP.NET MVC 3. I explain you the internal working of  granular request validation. Hope you will enjoy this article too.   SyntaxHighlighter.all()

  Read the article

• Using HTML 5 SessionState to save rendered Page Content

  - by Rick Strahl

  HTML 5 SessionState and LocalStorage are very useful and super easy to use to manage client side state. For building rich client side or SPA style applications it's a vital feature to be able to cache user data as well as HTML content in order to swap pages in and out of the browser's DOM. What might not be so obvious is that you can also use the sessionState and localStorage objects even in classic server rendered HTML applications to provide caching features between pages. These APIs have been around for a long time and are supported by most relatively modern browsers and even all the way back to IE8, so you can use them safely in your Web applications. SessionState and LocalStorage are easy The APIs that make up sessionState and localStorage are very simple. Both object feature the same API interface which  is a simple, string based key value store that has getItem, setItem, removeitem, clear and  key methods. The objects are also pseudo array objects and so can be iterated like an array with  a length property and you have array indexers to set and get values with. Basic usage  for storing and retrieval looks like this (using sessionStorage, but the syntax is the same for localStorage - just switch the objects):// set var lastAccess = new Date().getTime(); if (sessionStorage) sessionStorage.setItem("myapp_time", lastAccess.toString()); // retrieve in another page or on a refresh var time = null; if (sessionStorage) time = sessionStorage.getItem("myapp_time"); if (time) time = new Date(time * 1); else time = new Date(); sessionState stores data that is browser session specific and that has a liftetime of the active browser session or window. Shut down the browser or tab and the storage goes away. localStorage uses the same API interface, but the lifetime of the data is permanently stored in the browsers storage area until deleted via code or by clearing out browser cookies (not the cache). Both sessionStorage and localStorage space is limited. The spec is ambiguous about this - supposedly sessionStorage should allow for unlimited size, but it appears that most WebKit browsers support only 2.5mb for either object. This means you have to be careful what you store especially since other applications might be running on the same domain and also use the storage mechanisms. That said 2.5mb worth of character data is quite a bit and would go a long way. The easiest way to get a feel for how sessionState and localStorage work is to look at a simple example. You can go check out the following example online in Plunker: http://plnkr.co/edit/0ICotzkoPjHaWa70GlRZ?p=preview which looks like this: Plunker is an online HTML/JavaScript editor that lets you write and run Javascript code and similar to JsFiddle, but a bit cleaner to work in IMHO (thanks to John Papa for turning me on to it). The sample has two text boxes with counts that update session/local storage every time you click the related button. The counts are 'cached' in Session and Local storage. The point of these examples is that both counters survive full page reloads, and the LocalStorage counter survives a complete browser shutdown and restart. Go ahead and try it out by clicking the Reload button after updating both counters and then shutting down the browser completely and going back to the same URL (with the same browser). What you should see is that reloads leave both counters intact at the counted values, while a browser restart will leave only the local storage counter intact. The code to deal with the SessionStorage (and LocalStorage not shown here) in the example is isolated into a couple of wrapper methods to simplify the code: function getSessionCount() { var count = 0; if (sessionStorage) { var count = sessionStorage.getItem("ss_count"); count = !count ? 0 : count * 1; } $("#txtSession").val(count); return count; } function setSessionCount(count) { if (sessionStorage) sessionStorage.setItem("ss_count", count.toString()); } These two functions essentially load and store a session counter value. The two key methods used here are: sessionStorage.getItem(key); sessionStorage.setItem(key,stringVal); Note that the value given to setItem and return by getItem has to be a string. If you pass another type you get an error. Don't let that limit you though - you can easily enough store JSON data in a variable so it's quite possible to pass complex objects and store them into a single sessionStorage value:var user = { name: "Rick", id="ricks", level=8 } sessionStorage.setItem("app_user",JSON.stringify(user)); to retrieve it:var user = sessionStorage.getItem("app_user"); if (user) user = JSON.parse(user); Simple! If you're using the Chrome Developer Tools (F12) you can also check out the session and local storage state on the Resource tab:   You can also use this tool to refresh or remove entries from storage. What we just looked at is a purely client side implementation where a couple of counters are stored. For rich client centric AJAX applications sessionStorage and localStorage provide a very nice and simple API to store application state while the application is running. But you can also use these storage mechanisms to manage server centric HTML applications when you combine server rendering with some JavaScript to perform client side data caching. You can both store some state information and data on the client (ie. store a JSON object and carry it forth between server rendered HTML requests) or you can use it for good old HTTP based caching where some rendered HTML is saved and then restored later. Let's look at the latter with a real life example. Why do I need Client-side Page Caching for Server Rendered HTML? I don't know about you, but in a lot of my existing server driven applications I have lists that display a fair amount of data. Typically these lists contain links to then drill down into more specific data either for viewing or editing. You can then click on a link and go off to a detail page that provides more concise content. So far so good. But now you're done with the detail page and need to get back to the list, so you click on a 'bread crumbs trail' or an application level 'back to list' button and… …you end up back at the top of the list - the scroll position, the current selection in some cases even filters conditions - all gone with the wind. You've left behind the state of the list and are starting from scratch in your browsing of the list from the top. Not cool! Sound familiar? This a pretty common scenario with server rendered HTML content where it's so common to display lists to drill into, only to lose state in the process of returning back to the original list. Look at just about any traditional forums application, or even StackOverFlow to see what I mean here. Scroll down a bit to look at a post or entry, drill in then use the bread crumbs or tab to go back… In some cases returning to the top of a list is not a big deal. On StackOverFlow that sort of works because content is turning around so quickly you probably want to actually look at the top posts. Not always though - if you're browsing through a list of search topics you're interested in and drill in there's no way back to that position. Essentially anytime you're actively browsing the items in the list, that's when state becomes important and if it's not handled the user experience can be really disrupting. Content Caching If you're building client centric SPA style applications this is a fairly easy to solve problem - you tend to render the list once and then update the page content to overlay the detail content, only hiding the list temporarily until it's used again later. It's relatively easy to accomplish this simply by hiding content on the page and later making it visible again. But if you use server rendered content, hanging on to all the detail like filters, selections and scroll position is not quite as easy. Or is it??? This is where sessionStorage comes in handy. What if we just save the rendered content of a previous page, and then restore it when we return to this page based on a special flag that tells us to use the cached version? Let's see how we can do this. A real World Use Case Recently my local ISP asked me to help out with updating an ancient classifieds application. They had a very busy, local classifieds app that was originally an ASP classic application. The old app was - wait for it: frames based - and even though I lobbied against it, the decision was made to keep the frames based layout to allow rapid browsing of the hundreds of posts that are made on a daily basis. The primary reason they wanted this was precisely for the ability to quickly browse content item by item. While I personally hate working with Frames, I have to admit that the UI actually works well with the frames layout as long as you're running on a large desktop screen. You can check out the frames based desktop site here: http://classifieds.gorge.net/ However when I rebuilt the app I also added a secondary view that doesn't use frames. The main reason for this of course was for mobile displays which work horribly with frames. So there's a somewhat mobile friendly interface to the interface, which ditches the frames and uses some responsive design tweaking for mobile capable operation: http://classifeds.gorge.net/mobile  (or browse the base url with your browser width under 800px)   Here's what the mobile, non-frames view looks like:   As you can see this means that the list of classifieds posts now is a list and there's a separate page for drilling down into the item. And of course… originally we ran into that usability issue I mentioned earlier where the browse, view detail, go back to the list cycle resulted in lost list state. Originally in mobile mode you scrolled through the list, found an item to look at and drilled in to display the item detail. Then you clicked back to the list and BAM - you've lost your place. Because there are so many items added on a daily basis the full list is never fully loaded, but rather there's a "Load Additional Listings"  entry at the button. Not only did we originally lose our place when coming back to the list, but any 'additionally loaded' items are no longer there because the list was now rendering  as if it was the first page hit. The additional listings, and any filters, the selection of an item all were lost. Major Suckage! Using Client SessionStorage to cache Server Rendered Content To work around this problem I decided to cache the rendered page content from the list in SessionStorage. Anytime the list renders or is updated with Load Additional Listings, the page HTML is cached and stored in Session Storage. Any back links from the detail page or the login or write entry forms then point back to the list page with a back=true query string parameter. If the server side sees this parameter it doesn't render the part of the page that is cached. Instead the client side code retrieves the data from the sessionState cache and simply inserts it into the page. It sounds pretty simple, and the overall the process is really easy, but there are a few gotchas that I'll discuss in a minute. But first let's look at the implementation. Let's start with the server side here because that'll give a quick idea of the doc structure. As I mentioned the server renders data from an ASP.NET MVC view. On the list page when returning to the list page from the display page (or a host of other pages) looks like this: https://classifieds.gorge.net/list?back=True The query string value is a flag, that indicates whether the server should render the HTML. Here's what the top level MVC Razor view for the list page looks like:@model MessageListViewModel @{ ViewBag.Title = "Classified Listing"; bool isBack = !string.IsNullOrEmpty(Request.QueryString["back"]); } <form method="post" action="@Url.Action("list")"> <div id="SizingContainer"> @if (!isBack) { @Html.Partial("List_CommandBar_Partial", Model) <div id="PostItemContainer" class="scrollbox" xstyle="-webkit-overflow-scrolling: touch;"> @Html.Partial("List_Items_Partial", Model) @if (Model.RequireLoadEntry) { <div class="postitem loadpostitems" style="padding: 15px;"> <div id="LoadProgress" class="smallprogressright"></div> <div class="control-progress"> Load additional listings... </div> </div> } </div> } </div> </form> As you can see the query string triggers a conditional block that if set is simply not rendered. The content inside of #SizingContainer basically holds  the entire page's HTML sans the headers and scripts, but including the filter options and menu at the top. In this case this makes good sense - in other situations the fact that the menu or filter options might be dynamically updated might make you only cache the list rather than essentially the entire page. In this particular instance all of the content works and produces the proper result as both the list along with any filter conditions in the form inputs are restored. Ok, let's move on to the client. On the client there are two page level functions that deal with saving and restoring state. Like the counter example I showed earlier, I like to wrap the logic to save and restore values from sessionState into a separate function because they are almost always used in several places.page.saveData = function(id) { if (!sessionStorage) return; var data = { id: id, scroll: $("#PostItemContainer").scrollTop(), html: $("#SizingContainer").html() }; sessionStorage.setItem("list_html",JSON.stringify(data)); }; page.restoreData = function() { if (!sessionStorage) return; var data = sessionStorage.getItem("list_html"); if (!data) return null; return JSON.parse(data); }; The data that is saved is an object which contains an ID which is the selected element when the user clicks and a scroll position. These two values are used to reset the scroll position when the data is used from the cache. Finally the html from the #SizingContainer element is stored, which makes for the bulk of the document's HTML. In this application the HTML captured could be a substantial bit of data. If you recall, I mentioned that the server side code renders a small chunk of data initially and then gets more data if the user reads through the first 50 or so items. The rest of the items retrieved can be rather sizable. Other than the JSON deserialization that's Ok. Since I'm using SessionStorage the storage space has no immediate limits. Next is the core logic to handle saving and restoring the page state. At first though this would seem pretty simple, and in some cases it might be, but as the following code demonstrates there are a few gotchas to watch out for. Here's the relevant code I use to save and restore:$( function() { … var isBack = getUrlEncodedKey("back", location.href); if (isBack) { // remove the back key from URL setUrlEncodedKey("back", "", location.href); var data = page.restoreData(); // restore from sessionState if (!data) { // no data - force redisplay of the server side default list window.location = "list"; return; } $("#SizingContainer").html(data.html); var el = $(".postitem[data-id=" + data.id + "]"); $(".postitem").removeClass("highlight"); el.addClass("highlight"); $("#PostItemContainer").scrollTop(data.scroll); setTimeout(function() { el.removeClass("highlight"); }, 2500); } else if (window.noFrames) page.saveData(null); // save when page loads $("#SizingContainer").on("click", ".postitem", function() { var id = $(this).attr("data-id"); if (!id) return true; if (window.noFrames) page.saveData(id); var contentFrame = window.parent.frames["Content"]; if (contentFrame) contentFrame.location.href = "show/" + id; else window.location.href = "show/" + id; return false; }); … The code starts out by checking for the back query string flag which triggers restoring from the client cache. If cached the cached data structure is read from sessionStorage. It's important here to check if data was returned. If the user had back=true on the querystring but there is no cached data, he likely bookmarked this page or otherwise shut down the browser and came back to this URL. In that case the server didn't render any detail and we have no cached data, so all we can do is redirect to the original default list view using window.location. If we continued the page would render no data - so make sure to always check the cache retrieval result. Always! If there is data the it's loaded and the data.html data is restored back into the document by simply injecting the HTML back into the document's #SizingContainer element:$("#SizingContainer").html(data.html); It's that simple and it's quite quick even with a fully loaded list of additional items and on a phone. The actual HTML data is stored to the cache on every page load initially and then again when the user clicks on an element to navigate to a particular listing. The former ensures that the client cache always has something in it, and the latter updates with additional information for the selected element. For the click handling I use a data-id attribute on the list item (.postitem) in the list and retrieve the id from that. That id is then used to navigate to the actual entry as well as storing that Id value in the saved cached data. The id is used to reset the selection by searching for the data-id value in the restored elements. The overall process of this save/restore process is pretty straight forward and it doesn't require a bunch of code, yet it yields a huge improvement in the usability of the site on mobile devices (or anybody who uses the non-frames view). Some things to watch out for As easy as it conceptually seems to simply store and retrieve cached content, you have to be quite aware what type of content you are caching. The code above is all that's specific to cache/restore cycle and it works, but it took a few tweaks to the rest of the script code and server code to make it all work. There were a few gotchas that weren't immediately obvious. Here are a few things to pay attention to: Event Handling Logic Timing of manipulating DOM events Inline Script Code Bookmarking to the Cache Url when no cache exists Do you have inline script code in your HTML? That script code isn't going to run if you restore from cache and simply assign or it may not run at the time you think it would normally in the DOM rendering cycle. JavaScript Event Hookups The biggest issue I ran into with this approach almost immediately is that originally I had various static event handlers hooked up to various UI elements that are now cached. If you have an event handler like:$("#btnSearch").click( function() {…}); that works fine when the page loads with server rendered HTML, but that code breaks when you now load the HTML from cache. Why? Because the elements you're trying to hook those events to may not actually be there - yet. Luckily there's an easy workaround for this by using deferred events. With jQuery you can use the .on() event handler instead:$("#SelectionContainer").on("click","#btnSearch", function() {…}); which monitors a parent element for the events and checks for the inner selector elements to handle events on. This effectively defers to runtime event binding, so as more items are added to the document bindings still work. For any cached content use deferred events. Timing of manipulating DOM Elements Along the same lines make sure that your DOM manipulation code follows the code that loads the cached content into the page so that you don't manipulate DOM elements that don't exist just yet. Ideally you'll want to check for the condition to restore cached content towards the top of your script code, but that can be tricky if you have components or other logic that might not all run in a straight line. Inline Script Code Here's another small problem I ran into: I use a DateTime Picker widget I built a while back that relies on the jQuery date time picker. I also created a helper function that allows keyboard date navigation into it that uses JavaScript logic. Because MVC's limited 'object model' the only way to embed widget content into the page is through inline script. This code broken when I inserted the cached HTML into the page because the script code was not available when the component actually got injected into the page. As the last bullet - it's a matter of timing. There's no good work around for this - in my case I pulled out the jQuery date picker and relied on native <input type="date" /> logic instead - a better choice these days anyway, especially since this view is meant to be primarily to serve mobile devices which actually support date input through the browser (unlike desktop browsers of which only WebKit seems to support it). Bookmarking Cached Urls When you cache HTML content you have to make a decision whether you cache on the client and also not render that same content on the server. In the Classifieds app I didn't render server side content so if the user comes to the page with back=True and there is no cached content I have to a have a Plan B. Typically this happens when somebody ends up bookmarking the back URL. The easiest and safest solution for this scenario is to ALWAYS check the cache result to make sure it exists and if not have a safe URL to go back to - in this case to the plain uncached list URL which amounts to effectively redirecting. This seems really obvious in hindsight, but it's easy to overlook and not see a problem until much later, when it's not obvious at all why the page is not rendering anything. Don't use <body> to replace Content Since we're practically replacing all the HTML in the page it may seem tempting to simply replace the HTML content of the <body> tag. Don't. The body tag usually contains key things that should stay in the page and be there when it loads. Specifically script tags and elements and possibly other embedded content. It's best to create a top level DOM element specifically as a placeholder container for your cached content and wrap just around the actual content you want to replace. In the app above the #SizingContainer is that container. Other Approaches The approach I've used for this application is kind of specific to the existing server rendered application we're running and so it's just one approach you can take with caching. However for server rendered content caching this is a pattern I've used in a few apps to retrofit some client caching into list displays. In this application I took the path of least resistance to the existing server rendering logic. Here are a few other ways that come to mind: Using Partial HTML Rendering via AJAXInstead of rendering the page initially on the server, the page would load empty and the client would render the UI by retrieving the respective HTML and embedding it into the page from a Partial View. This effectively makes the initial rendering and the cached rendering logic identical and removes the server having to decide whether this request needs to be rendered or not (ie. not checking for a back=true switch). All the logic related to caching is made on the client in this case. Using JSON Data and Client RenderingThe hardcore client option is to do the whole UI SPA style and pull data from the server and then use client rendering or databinding to pull the data down and render using templates or client side databinding with knockout/angular et al. As with the Partial Rendering approach the advantage is that there's no difference in the logic between pulling the data from cache or rendering from scratch other than the initial check for the cache request. Of course if the app is a  full on SPA app, then caching may not be required even - the list could just stay in memory and be hidden and reactivated. I'm sure there are a number of other ways this can be handled as well especially using  AJAX. AJAX rendering might simplify the logic, but it also complicates search engine optimization since there's no content loaded initially. So there are always tradeoffs and it's important to look at all angles before deciding on any sort of caching solution in general. State of the Session SessionState and LocalStorage are easy to use in client code and can be integrated even with server centric applications to provide nice caching features of content and data. In this post I've shown a very specific scenario of storing HTML content for the purpose of remembering list view data and state and making the browsing experience for lists a bit more friendly, especially if there's dynamically loaded content involved. If you haven't played with sessionStorage or localStorage I encourage you to give it a try. There's a lot of cool stuff that you can do with this beyond the specific scenario I've covered here… Resources Overview of localStorage (also applies to sessionStorage) Web Storage Compatibility Modernizr Test Suite© Rick Strahl, West Wind Technologies, 2005-2013Posted in JavaScript  HTML5  ASP.NET  MVC   Tweet !function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0];if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src="//platform.twitter.com/widgets.js";fjs.parentNode.insertBefore(js,fjs);}}(document,"script","twitter-wjs"); (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();

  Read the article

• Problem Solving: Algorithm Required Urgently, Plz Help

  - by user616417

  Problem Solving: I've been working on something since last week. I am stuck at a point, where I want to find the minimum number of airplanes required to carry out a flight schedule given below. Plz, try out the brainstorming, i need the algorithm really badly, i'm also short of time. Thank u in advance. The Schedule---- Flight #,From,To,Departure,Arrival,Days,Via 6E 204,Agartala,Delhi,10:15:00,13:55:00,Daily,Kolkata 6E 360,Agartala,Imphal,13:50:00,14:35:00,Mo Th Sa, 6E 204,Agartala,Kolkata,10:15:00,11:00:00,Daily, 6E 360,Agartala,Kolkata,13:50:00,16:15:00,Mo Th Sa,Imphal 6E 362,Agartala,Kolkata,15:25:00,16:15:00,Tu We Fr Su, 6E 153,Ahmedabad,Bangalore,17:00:00,19:00:00,Daily, 6E 212,Ahmedabad,Chennai,9:00:00,12:55:00,Daily,Mumbai 6E 154,Ahmedabad,Delhi,12:30:00,14:00:00,Daily, 6E 211,Ahmedabad,Jaipur,19:10:00,20:20:00,Daily, 6E 410,Ahmedabad,Kolkata,15:00:00,17:30:00,Daily, 6E 212,Ahmedabad,Mumbai,9:00:00,10:10:00,Daily, 6E 409,Ahmedabad,Pune,14:25:00,15:40:00,Ex Sat, 6E 154,Bangalore,Ahmedabad,10:00:00,12:00:00,Daily, 6E 277,Bangalore,Chennai,15:35:00,16:25:00,Daily, 6E 132,Bangalore,Delhi,6:00:00,8:25:00,Daily, 6E 102,Bangalore,Delhi,9:50:00,13:45:00,Ex Sat,Pune 6E 154,Bangalore,Delhi,10:00:00,14:00:00,Daily,Ahmedabad 6E 104,Bangalore,Delhi,11:30:00,14:10:00,Sat, 6E 122,Bangalore,Delhi,17:20:00,20:00:00,Daily, 6E 108,Bangalore,Delhi,19:20:00,23:10:00,Sat,Pune 6E 106,Bangalore,Delhi,19:30:00,22:00:00,Ex Sat, 6E 275,Bangalore,Goa,12:15:00,13:15:00,Daily, 6E 351,Bangalore,Hyderabad,8:25:00,9:25:00,Daily, 6E 152,Bangalore,Hyderabad,19:10:00,20:10:00,Ex Sat, 6E 152,Bangalore,Hyderabad,19:30:00,20:35:00,Sat, 6E 152,Bangalore,Jaipur,19:10:00,22:30:00,Ex Sat,Hyderabad 6E 152,Bangalore,Jaipur,19:30:00,22:30:00,Sat,Hyderabad 6E 351,Bangalore,Kolkata,8:25:00,11:55:00,Daily,Hyderabad 6E 277,Bangalore,Kolkata,15:35:00,19:15:00,Daily,Chennai 6E 402,Bangalore,Mumbai,6:05:00,7:45:00,Daily, 6E 275,Bangalore,Mumbai,12:15:00,14:45:00,Daily,Goa 6E 414,Bangalore,Mumbai,12:45:00,14:20:00,Daily, 6E 412,Bangalore,Mumbai,21:20:00,23:20:00,Daily, 6E 102,Bangalore,Pune,9:50:00,11:10:00,Ex Sat, 6E 108,Bangalore,Pune,19:20:00,20:40:00,Sat, 6E 258,Bhubaneshwar,Delhi,18:55:00,20:55:00,Daily, 6E 257,Bhubaneshwar,Hyderabad,10:40:00,12:05:00,Daily, 6E 257,Bhubaneshwar,Mumbai,10:40:00,13:50:00,Daily,Hyderabad 6E 211,Chennai,Ahmedabad,15:10:00,18:40:00,Daily,Mumbai 6E 275,Chennai,Bangalore,10:50:00,11:40:00,Daily, 6E 302,Chennai,Delhi,11:35:00,15:20:00,Daily,Hyderabad 6E 282,Chennai,Delhi,19:45:00,22:30:00,Daily, 6E 275,Chennai,Goa,10:50:00,13:15:00,Daily,Bangalore 6E 302,Chennai,Hyderabad,11:35:00,12:40:00,Daily, 6E 211,Chennai,Jaipur,15:10:00,20:20:00,Daily,Mumbai/Ahmedabad 6E 523,Chennai,Kolkata,8:20:00,10:30:00,Daily, 6E 277,Chennai,Kolkata,16:55:00,19:15:00,Daily, 6E 211,Chennai,Mumbai,15:10:00,16:50:00,Daily, 6E 524,Chennai,Pune,21:15:00,23:00:00,Daily, 6E 273,Delhi,Agartala,6:15:00,9:45:00,Daily,Kolkata 6E 153,Delhi,Ahmedabad,14:45:00,16:30:00,Daily, 6E 101,Delhi,Bangalore,6:30:00,9:10:00,Ex Sat, 6E 103,Delhi,Bangalore,6:45:00,10:40:00,Sat,Pune 6E 121,Delhi,Bangalore,9:30:00,12:10:00,Daily, 6E 105,Delhi,Bangalore,14:20:00,18:30:00,Ex Sat,Pune 6E 153,Delhi,Bangalore,14:45:00,19:00:00,Daily,Ahmedabad 6E 107,Delhi,Bangalore,15:55:00,18:40:00,Sat, 6E 131,Delhi,Bangalore,20:45:00,23:15:00,Daily, 6E 257,Delhi,Bhubaneshwar,8:10:00,10:10:00,Daily, 6E 301,Delhi,Chennai,7:00:00,11:05:00,Daily,Hyderabad 6E 283,Delhi,Chennai,16:30:00,19:05:00,Daily, 6E 181,Delhi,Goa,9:15:00,13:35:00,Daily,Mumbai 6E 333,Delhi,Goa,11:45:00,14:15:00,Daily, 6E 201,Delhi,Guwahati,5:30:00,7:50:00,Daily, 6E 301,Delhi,Hyderabad,7:00:00,9:00:00,Daily, 6E 257,Delhi,Hyderabad,8:10:00,12:05:00,Daily,Bhubaneshwar 6E 305,Delhi,Hyderabad,14:00:00,15:55:00,Daily, 6E 307,Delhi,Hyderabad,21:00:00,22:55:00,Daily, 6E 201,Delhi,Imphal,5:30:00,9:10:00,Daily,Guwahati 6E 305,Delhi,Kochi,14:00:00,18:25:00,Daily,Hyderabad 6E 273,Delhi,Kolkata,6:15:00,8:20:00,Daily, 6E 203,Delhi,Kolkata,15:00:00,17:05:00,Daily, 6E 209,Delhi,Kolkata,18:30:00,20:45:00,Daily, 6E 183,Delhi,Mumbai,6:45:00,8:35:00,Daily, 6E 181,Delhi,Mumbai,9:15:00,11:35:00,Daily, 6E 481,Delhi,Mumbai,10:50:00,13:50:00,Daily,Vadodara 6E 189,Delhi,Mumbai,14:45:00,16:50:00,Daily, 6E 187,Delhi,Mumbai,17:50:00,19:50:00,Daily, 6E 185,Delhi,Mumbai,20:15:00,22:20:00,Daily, 6E 135,Delhi,Nagpur,8:55:00,10:40:00,Ex Sat, 6E 103,Delhi,Pune,6:45:00,8:45:00,Sat, 6E 135,Delhi,Pune,8:55:00,12:30:00,Ex Sat,Nagpur 6E 105,Delhi,Pune,14:20:00,16:30:00,Ex Sat, 6E 481,Delhi,Vadodara,10:50:00,12:20:00,Daily, 6E 277,Goa,Bangalore,14:05:00,15:00:00,Daily, 6E 277,Goa,Chennai,14:05:00,16:25:00,Daily,Bangalore 6E 334,Goa,Delhi,14:45:00,17:10:00,Daily, 6E 277,Goa,Kolkata,14:05:00,19:15:00,Daily,Bangalore/Chennai 6E 275,Goa,Mumbai,13:45:00,14:45:00,Daily, 6E 202,Guwahati,Delhi,11:00:00,13:25:00,Daily, 6E 201,Guwahati,Imphal,8:25:00,9:10:00,Daily, 6E 208,Guwahati,Jaipur,12:40:00,16:55:00,Daily,Kolkata 6E 208,Guwahati,Kolkata,12:40:00,14:00:00,Daily, 6E 322,Guwahati,Kolkata,15:30:00,16:50:00,Daily, 6E 322,Guwahati,Mumbai,15:30:00,20:20:00,Daily,Kolkata 6E 151,Hyderabad,Bangalore,8:20:00,9:20:00,Daily, 6E 352,Hyderabad,Bangalore,19:40:00,20:40:00,Daily, 6E 258,Hyderabad,Bhubaneshwar,16:40:00,18:20:00,Daily, 6E 301,Hyderabad,Chennai,9:50:00,11:05:00,Daily, 6E 308,Hyderabad,Delhi,6:10:00,8:00:00,Daily, 6E 302,Hyderabad,Delhi,13:10:00,15:20:00,Daily, 6E 258,Hyderabad,Delhi,16:40:00,20:55:00,Daily,Bhubaneshwar 6E 306,Hyderabad,Delhi,21:00:00,23:05:00,Daily, 6E 152,Hyderabad,Jaipur,20:50:00,22:30:00,Ex Sat, 6E 152,Hyderabad,Jaipur,21:10:00,22:30:00,Sat, 6E 305,Hyderabad,Kochi,16:45:00,18:25:00,Daily, 6E 351,Hyderabad,Kolkata,9:55:00,11:55:00,Daily, 6E 257,Hyderabad,Mumbai,12:35:00,13:50:00,Daily, 6E 362,Imphal,Agartala,14:15:00,14:55:00,Tu We Fr Su, 6E 202,Imphal,Delhi,9:40:00,13:25:00,Daily,Guwahati 6E 202,Imphal,Guwahati,9:40:00,10:25:00,Daily, 6E 362,Imphal,Kolkata,14:15:00,16:15:00,Tu We Fr Su,Agartala 6E 360,Imphal,Kolkata,15:05:00,16:15:00,Mo Th Sa, 6E 212,Jaipur,Ahmedabad,7:30:00,8:35:00,Daily, 6E 151,Jaipur,Bangalore,6:00:00,9:20:00,Daily,Hyderabad 6E 212,Jaipur,Chennai,7:30:00,12:55:00,Daily,Mumbai/Ahmedabad 6E 207,Jaipur,Guwahati,8:20:00,12:10:00,Daily,Kolkata 6E 151,Jaipur,Hyderabad,6:00:00,7:40:00,Daily, 6E 207,Jaipur,Kolkata,8:20:00,10:10:00,Daily, 6E 323,Jaipur,Kolkata,17:35:00,23:00:00,Daily,Mumbai 6E 212,Jaipur,Mumbai,7:30:00,10:10:00,Daily,Ahmedabad 6E 323,Jaipur,Mumbai,17:35:00,19:15:00,Daily, 6E 306,Kochi,Delhi,19:00:00,23:05:00,Daily,Hyderabad 6E 306,Kochi,Hyderabad,19:00:00,20:30:00,Daily, 6E 273,Kolkata,Agartala,8:50:00,9:45:00,Daily, 6E 360,Kolkata,Agartala,12:30:00,13:20:00,Mo Th Sa, 6E 362,Kolkata,Agartala,12:30:00,14:55:00,TuWeFrSu,Imphal 6E 409,Kolkata,Ahmedabad,11:10:00,13:50:00,Daily, 6E 275,Kolkata,Bangalore,7:30:00,11:40:00,Daily,Chennai 6E 352,Kolkata,Bangalore,16:50:00,20:40:00,Daily,Hyderabad 6E 275,Kolkata,Chennai,7:30:00,9:50:00,Daily, 6E 524,Kolkata,Chennai,18:15:00,20:25:00,Daily, 6E 210,Kolkata,Delhi,7:45:00,10:05:00,Daily, 6E 204,Kolkata,Delhi,11:40:00,13:55:00,Daily, 6E 274,Kolkata,Delhi,19:45:00,22:10:00,Daily, 6E 275,Kolkata,Goa,7:30:00,13:15:00,Daily,Chennai/Bangalore 6E 207,Kolkata,Guwahati,10:50:00,12:10:00,Daily, 6E 321,Kolkata,Guwahati,13:00:00,14:20:00,Daily, 6E 352,Kolkata,Hyderabad,16:50:00,19:00:00,Daily, 6E 362,Kolkata,Imphal,12:30:00,13:45:00,Tu We Fr Su, 6E 360,Kolkata,Imphal,12:30:00,14:35:00,MoThSa,Agartala 6E 208,Kolkata,Jaipur,14:35:00,16:55:00,Daily, 6E 320,Kolkata,Mumbai,6:00:00,8:30:00,Daily, 6E 322,Kolkata,Mumbai,17:35:00,20:20:00,Daily, 6E 404,Kolkata,Mumbai,18:35:00,21:55:00,Daily,Nagpur 6E 404,Kolkata,Nagpur,18:35:00,20:05:00,Daily, 6E 409,Kolkata,Pune,11:10:00,15:40:00,Ex Sat,Ahmedabad 6E 524,Kolkata,Pune,18:15:00,23:00:00,Daily,Chennai 6E 211,Mumbai,Ahmedabad,17:40:00,18:40:00,Daily, 6E 411,Mumbai,Bangalore,6:20:00,7:50:00,Daily, 6E 413,Mumbai,Bangalore,15:00:00,16:40:00,Daily, 6E 415,Mumbai,Bangalore,21:05:00,22:40:00,Daily, 6E 258,Mumbai,Bhubaneshwar,14:30:00,18:20:00,Daily,Hyderabad 6E 212,Mumbai,Chennai,11:00:00,12:55:00,Daily, 6E 184,Mumbai,Delhi,6:15:00,8:15:00,Daily, 6E 180,Mumbai,Delhi,8:25:00,10:35:00,Daily, 6E 482,Mumbai,Delhi,9:25:00,12:35:00,Daily,Vadodara 6E 188,Mumbai,Delhi,14:25:00,16:35:00,Daily, 6E 186,Mumbai,Delhi,17:50:00,19:55:00,Daily, 6E 182,Mumbai,Delhi,21:15:00,23:20:00,Daily, 6E 181,Mumbai,Goa,12:35:00,13:35:00,Daily, 6E 321,Mumbai,Guwahati,9:20:00,14:20:00,Daily,Kolkata 6E 258,Mumbai,Hyderabad,14:30:00,16:00:00,Daily, 6E 207,Mumbai,Jaipur,5:55:00,7:40:00,Daily, 6E 211,Mumbai,Jaipur,17:40:00,20:20:00,Daily,Ahmedabad 6E 207,Mumbai,Kolkata,5:55:00,10:10:00,Daily,Jaipur 6E 321,Mumbai,Kolkata,9:20:00,12:00:00,Daily, 6E 403,Mumbai,Kolkata,15:35:00,18:50:00,Daily,Nagpur 6E 323,Mumbai,Kolkata,20:05:00,23:00:00,Daily, 6E 403,Mumbai,Nagpur,15:35:00,16:50:00,Daily, 6E 482,Mumbai,Vadodara,9:25:00,10:25:00,Daily, 6E 136,Nagpur,Delhi,18:10:00,19:40:00,Ex Sat, 6E 403,Nagpur,Kolkata,17:20:00,18:50:00,Daily, 6E 404,Nagpur,Mumbai,20:35:00,21:55:00,Daily, 6E 135,Nagpur,Pune,11:20:00,12:30:00,Ex Sat, 6E 410,Pune,Ahmedabad,13:10:00,14:30:00,Ex Sat, 6E 103,Pune,Bangalore,9:15:00,10:40:00,Sat, 6E 105,Pune,Bangalore,17:00:00,18:30:00,Ex Sat, 6E 523,Pune,Chennai,5:55:00,7:40:00,Daily, 6E 102,Pune,Delhi,11:45:00,13:45:00,Ex Sat, 6E 136,Pune,Delhi,16:15:00,19:40:00,Ex Sat,Nagpur 6E 108,Pune,Delhi,21:10:00,23:10:00,Sat, 6E 523,Pune,Kolkata,5:55:00,10:30:00,Daily,Chennai 6E 410,Pune,Kolkata,13:10:00,17:30:00,Ex Sat,Ahmedabad 6E 136,Pune,Nagpur,16:15:00,17:40:00,Ex Sat, 6E 482,Vadodara,Delhi,10:55:00,12:35:00,Daily, 6E 481,Vadodara,Mumbai,12:50:00,13:50:00,Daily,

  Read the article

• how to properly transfer user input from index to invoice?

  - by Romel

  I got a dillema, I'm trying to find a solution for my code. How do I make it so that when the user inputs a given quantity in the text box from the index.php it will transfer that input quantity to the invoice.php. I've tried doing the post method but it seems like it's not working :/ As always, any help or suggestions will be greatly appreciated! I hope it's something simple:( Here's my code: index.php <html> <style> body{ background-image: url('URL HERE'); font-family: "Helvetica"; font-size:15px; } h1{ color:black; text-align:center; } p{ font-size:15px; } </style> <h1> STORE TITLE HERE </h1> <body> <form action="login.php" method="post"> <?php //Include products info.inc (Which holds all our product arrays and info) //Credit: Tracy & Mark (THank you!) include 'products_info.inc'; /*The following code centers my table on the page, makes the table background white, makes the table 50% of the browser window, gives it a border of 1 px, gives a padding of 2 px between the cell border and content, and gives 1 px of spacing between cells. */ echo "<table align=center bgcolor='FFFFFF' width=50% border=1 cellpadding=1 cellspacing=2>"; //Credit: Tracy & Mark (THank you!) echo '<th>Product</th> <th>Description</th> <th>Price</th> <th>Quantity</th>'; //The following code loops through the whole table body and then prints each row. for($i=0; $i<count($allfood); $i++) { //Credit: Tracy & Mark (THank you!) echo "<tr align=center>"; echo "<td>{$allfood[$i]['Product']}</td>"; echo "<td>{$allfood[$i]['Description']}</td>"; echo "<td>{$allfood[$i]['Price']}</td>"; echo "<td>{$allfood[$i]['Quantity']}</td>"; echo "</tr>"; } //This code ends the table. echo "</table>"; echo "<br>"; ?> <br><center><input type='submit' name='purchase' value='Purchase'></center> </form> </body> </html> And here's my invoice.php <html> <style> body{ background-image: url('URL HERE'); font-family: "Helvetica"; font-size:15px; } h1{ color:black; text-align:center; } p{ font-size:15px; } </style> <h1> Invoice </h1> </html> <?php //Include products info.inc (Which holds all our product arrays and info) //Credit: Tracy & Mark (Thank you!) include 'products_info.inc'; //Display the invoice & 'WELCOME USER. THANK YOU FOR USING THIS DAMN THING msg' /*The following code centers my invoice table on the page, makes the table background white, makes the table 50% of the browser window, gives it a border of 1 px, gives a padding of 2 px between the cell border and content, and gives 1 px of spacing between cells. */ echo "<table align=center bgcolor='FFFFFF' width=50% border=1 cellpadding=1cellspacing=2>"; echo "<tr>"; echo "<td align=center><b>Product</b></td>"; echo "<td align=center><b>Quantity</b></td>"; echo "<td align=center><b>Price</></td>"; echo "<td align=center><b>Extended Price</b></td>"; echo "</tr>"; for($i=0; $i<count($allfood); $i++) { //Credit: Tracy & Mark (Thank you!) $qty= @$_POST['Quantity']['$i']; // This calculates the price if the user orders more than 1 item. $extendedprice = $qty*$allfood[$i]['Price']; echo "<tr>"; echo "<td align=center>{$allfood[$i]['Product']}</td>"; echo "<td align=center>$extendedprice</td>"; echo "<td align=center>{$allfood[$i]['Price']}</td>"; echo "</tr>"; } // The goal here was to make it so that if the user selected a certain quantity from index.php, it would carry over and display on the invoice.php if ($qty = 0) { echo "please choose 1"; } elseif ($qty > 0) { echo $qty; } /*echo "<tr>"; echo "<td align=center>Subtotal</b></td>"; echo "<td align=center></td>"; echo "<td align=center></td>"; echo "<tr>"; echo "<td align=center>Tax at 5.75%</td>"; echo "<td align=center></td>"; echo "<td align=center></td>"; echo "<tr>"; echo "<td align=center><b>Grand total</b></td>"; echo "<td align=center></td>"; echo "<td align=center></td>"; */ echo "</table>"; ?> <br> <center> <form action="index.php" method="post"> <input type="submit" name="home" value="Back to homepage"> </form> </center>

  Read the article

• How do I improve my performance with this singly linked list struct within my program?

  - by Jesus

  Hey guys, I have a program that does operations of sets of strings. We have to implement functions such as addition and subtraction of two sets of strings. We are suppose to get it down to the point where performance if of O(N+M), where N,M are sets of strings. Right now, I believe my performance is at O(N*M), since I for each element of N, I go through every element of M. I'm particularly focused on getting the subtraction to the proper performance, as if I can get that down to proper performance, I believe I can carry that knowledge over to the rest of things I have to implement. The '-' operator is suppose to work like this, for example. Declare set1 to be an empty set. Declare set2 to be a set with { a b c } elements Declare set3 to be a set with ( b c d } elements set1 = set2 - set3 And now set1 is suppose to equal { a }. So basically, just remove any element from set3, that is also in set2. For the addition implementation (overloaded '+' operator), I also do the sorting of the strings (since we have to). All the functions work right now btw. So I was wondering if anyone could a) Confirm that currently I'm doing O(N*M) performance b) Give me some ideas/implementations on how to improve the performance to O(N+M) Note: I cannot add any member variables or functions to the class strSet or to the node structure. The implementation of the main program isn't very important, but I will post the code for my class definition and the implementation of the member functions: strSet2.h (Implementation of my class and struct) // Class to implement sets of strings // Implements operators for union, intersection, subtraction, // etc. for sets of strings // V1.1 15 Feb 2011 Added guard (#ifndef), deleted using namespace RCH #ifndef _STRSET_ #define _STRSET_ #include <iostream> #include <vector> #include <string> // Deleted: using namespace std; 15 Feb 2011 RCH struct node { std::string s1; node * next; }; class strSet { private: node * first; public: strSet (); // Create empty set strSet (std::string s); // Create singleton set strSet (const strSet &copy); // Copy constructor ~strSet (); // Destructor int SIZE() const; bool isMember (std::string s) const; strSet operator + (const strSet& rtSide); // Union strSet operator - (const strSet& rtSide); // Set subtraction strSet& operator = (const strSet& rtSide); // Assignment }; // End of strSet class #endif // _STRSET_ strSet2.cpp (implementation of member functions) #include <iostream> #include <vector> #include <string> #include "strset2.h" using namespace std; strSet::strSet() { first = NULL; } strSet::strSet(string s) { node *temp; temp = new node; temp->s1 = s; temp->next = NULL; first = temp; } strSet::strSet(const strSet& copy) { if(copy.first == NULL) { first = NULL; } else { node *n = copy.first; node *prev = NULL; while (n) { node *newNode = new node; newNode->s1 = n->s1; newNode->next = NULL; if (prev) { prev->next = newNode; } else { first = newNode; } prev = newNode; n = n->next; } } } strSet::~strSet() { if(first != NULL) { while(first->next != NULL) { node *nextNode = first->next; first->next = nextNode->next; delete nextNode; } } } int strSet::SIZE() const { int size = 0; node *temp = first; while(temp!=NULL) { size++; temp=temp->next; } return size; } bool strSet::isMember(string s) const { node *temp = first; while(temp != NULL) { if(temp->s1 == s) { return true; } temp = temp->next; } return false; } strSet strSet::operator + (const strSet& rtSide) { strSet newSet; newSet = *this; node *temp = rtSide.first; while(temp != NULL) { string newEle = temp->s1; if(!isMember(newEle)) { if(newSet.first==NULL) { node *newNode; newNode = new node; newNode->s1 = newEle; newNode->next = NULL; newSet.first = newNode; } else if(newSet.SIZE() == 1) { if(newEle < newSet.first->s1) { node *tempNext = newSet.first; node *newNode; newNode = new node; newNode->s1 = newEle; newNode->next = tempNext; newSet.first = newNode; } else { node *newNode; newNode = new node; newNode->s1 = newEle; newNode->next = NULL; newSet.first->next = newNode; } } else { node *prev = NULL; node *curr = newSet.first; while(curr != NULL) { if(newEle < curr->s1) { if(prev == NULL) { node *newNode; newNode = new node; newNode->s1 = newEle; newNode->next = curr; newSet.first = newNode; break; } else { node *newNode; newNode = new node; newNode->s1 = newEle; newNode->next = curr; prev->next = newNode; break; } } if(curr->next == NULL) { node *newNode; newNode = new node; newNode->s1 = newEle; newNode->next = NULL; curr->next = newNode; break; } prev = curr; curr = curr->next; } } } temp = temp->next; } return newSet; } strSet strSet::operator - (const strSet& rtSide) { strSet newSet; newSet = *this; node *temp = rtSide.first; while(temp != NULL) { string element = temp->s1; node *prev = NULL; node *curr = newSet.first; while(curr != NULL) { if( element < curr->s1 ) break; if( curr->s1 == element ) { if( prev == NULL) { node *duplicate = curr; newSet.first = newSet.first->next; delete duplicate; break; } else { node *duplicate = curr; prev->next = curr->next; delete duplicate; break; } } prev = curr; curr = curr->next; } temp = temp->next; } return newSet; } strSet& strSet::operator = (const strSet& rtSide) { if(this != &rtSide) { if(first != NULL) { while(first->next != NULL) { node *nextNode = first->next; first->next = nextNode->next; delete nextNode; } } if(rtSide.first == NULL) { first = NULL; } else { node *n = rtSide.first; node *prev = NULL; while (n) { node *newNode = new node; newNode->s1 = n->s1; newNode->next = NULL; if (prev) { prev->next = newNode; } else { first = newNode; } prev = newNode; n = n->next; } } } return *this; }

  Read the article

• How John Got 15x Improvement Without Really Trying

  - by rchrd

  The following article was published on a Sun Microsystems website a number of years ago by John Feo. It is still useful and worth preserving. So I'm republishing it here.  How I Got 15x Improvement Without Really Trying John Feo, Sun Microsystems Taking ten "personal" program codes used in scientific and engineering research, the author was able to get from 2 to 15 times performance improvement easily by applying some simple general optimization techniques. Introduction Scientific research based on computer simulation depends on the simulation for advancement. The research can advance only as fast as the computational codes can execute. The codes' efficiency determines both the rate and quality of results. In the same amount of time, a faster program can generate more results and can carry out a more detailed simulation of physical phenomena than a slower program. Highly optimized programs help science advance quickly and insure that monies supporting scientific research are used as effectively as possible. Scientific computer codes divide into three broad categories: ISV, community, and personal. ISV codes are large, mature production codes developed and sold commercially. The codes improve slowly over time both in methods and capabilities, and they are well tuned for most vendor platforms. Since the codes are mature and complex, there are few opportunities to improve their performance solely through code optimization. Improvements of 10% to 15% are typical. Examples of ISV codes are DYNA3D, Gaussian, and Nastran. Community codes are non-commercial production codes used by a particular research field. Generally, they are developed and distributed by a single academic or research institution with assistance from the community. Most users just run the codes, but some develop new methods and extensions that feed back into the general release. The codes are available on most vendor platforms. Since these codes are younger than ISV codes, there are more opportunities to optimize the source code. Improvements of 50% are not unusual. Examples of community codes are AMBER, CHARM, BLAST, and FASTA. Personal codes are those written by single users or small research groups for their own use. These codes are not distributed, but may be passed from professor-to-student or student-to-student over several years. They form the primordial ocean of applications from which community and ISV codes emerge. Government research grants pay for the development of most personal codes. This paper reports on the nature and performance of this class of codes. Over the last year, I have looked at over two dozen personal codes from more than a dozen research institutions. The codes cover a variety of scientific fields, including astronomy, atmospheric sciences, bioinformatics, biology, chemistry, geology, and physics. The sources range from a few hundred lines to more than ten thousand lines, and are written in Fortran, Fortran 90, C, and C++. For the most part, the codes are modular, documented, and written in a clear, straightforward manner. They do not use complex language features, advanced data structures, programming tricks, or libraries. I had little trouble understanding what the codes did or how data structures were used. Most came with a makefile. Surprisingly, only one of the applications is parallel. All developers have access to parallel machines, so availability is not an issue. Several tried to parallelize their applications, but stopped after encountering difficulties. Lack of education and a perception that parallelism is difficult prevented most from trying. I parallelized several of the codes using OpenMP, and did not judge any of the codes as difficult to parallelize. Even more surprising than the lack of parallelism is the inefficiency of the codes. I was able to get large improvements in performance in a matter of a few days applying simple optimization techniques. Table 1 lists ten representative codes [names and affiliation are omitted to preserve anonymity]. Improvements on one processor range from 2x to 15.5x with a simple average of 4.75x. I did not use sophisticated performance tools or drill deep into the program's execution character as one would do when tuning ISV or community codes. Using only a profiler and source line timers, I identified inefficient sections of code and improved their performance by inspection. The changes were at a high level. I am sure there is another factor of 2 or 3 in each code, and more if the codes are parallelized. The study’s results show that personal scientific codes are running many times slower than they should and that the problem is pervasive. Computational scientists are not sloppy programmers; however, few are trained in the art of computer programming or code optimization. I found that most have a working knowledge of some programming language and standard software engineering practices; but they do not know, or think about, how to make their programs run faster. They simply do not know the standard techniques used to make codes run faster. In fact, they do not even perceive that such techniques exist. The case studies described in this paper show that applying simple, well known techniques can significantly increase the performance of personal codes. It is important that the scientific community and the Government agencies that support scientific research find ways to better educate academic scientific programmers. The inefficiency of their codes is so bad that it is retarding both the quality and progress of scientific research. # cacheperformance redundantoperations loopstructures performanceimprovement 1 x x 15.5 2 x 2.8 3 x x 2.5 4 x 2.1 5 x x 2.0 6 x 5.0 7 x 5.8 8 x 6.3 9 2.2 10 x x 3.3 Table 1 — Area of improvement and performance gains of 10 codes The remainder of the paper is organized as follows: sections 2, 3, and 4 discuss the three most common sources of inefficiencies in the codes studied. These are cache performance, redundant operations, and loop structures. Each section includes several examples. The last section summaries the work and suggests a possible solution to the issues raised. Optimizing cache performance Commodity microprocessor systems use caches to increase memory bandwidth and reduce memory latencies. Typical latencies from processor to L1, L2, local, and remote memory are 3, 10, 50, and 200 cycles, respectively. Moreover, bandwidth falls off dramatically as memory distances increase. Programs that do not use cache effectively run many times slower than programs that do. When optimizing for cache, the biggest performance gains are achieved by accessing data in cache order and reusing data to amortize the overhead of cache misses. Secondary considerations are prefetching, associativity, and replacement; however, the understanding and analysis required to optimize for the latter are probably beyond the capabilities of the non-expert. Much can be gained simply by accessing data in the correct order and maximizing data reuse. 6 out of the 10 codes studied here benefited from such high level optimizations. Array Accesses The most important cache optimization is the most basic: accessing Fortran array elements in column order and C array elements in row order. Four of the ten codes—1, 2, 4, and 10—got it wrong. Compilers will restructure nested loops to optimize cache performance, but may not do so if the loop structure is too complex, or the loop body includes conditionals, complex addressing, or function calls. In code 1, the compiler failed to invert a key loop because of complex addressing do I = 0, 1010, delta_x IM = I - delta_x IP = I + delta_x do J = 5, 995, delta_x JM = J - delta_x JP = J + delta_x T1 = CA1(IP, J) + CA1(I, JP) T2 = CA1(IM, J) + CA1(I, JM) S1 = T1 + T2 - 4 * CA1(I, J) CA(I, J) = CA1(I, J) + D * S1 end do end do In code 2, the culprit is conditionals do I = 1, N do J = 1, N If (IFLAG(I,J) .EQ. 0) then T1 = Value(I, J-1) T2 = Value(I-1, J) T3 = Value(I, J) T4 = Value(I+1, J) T5 = Value(I, J+1) Value(I,J) = 0.25 * (T1 + T2 + T5 + T4) Delta = ABS(T3 - Value(I,J)) If (Delta .GT. MaxDelta) MaxDelta = Delta endif enddo enddo I fixed both programs by inverting the loops by hand. Code 10 has three-dimensional arrays and triply nested loops. The structure of the most computationally intensive loops is too complex to invert automatically or by hand. The only practical solution is to transpose the arrays so that the dimension accessed by the innermost loop is in cache order. The arrays can be transposed at construction or prior to entering a computationally intensive section of code. The former requires all array references to be modified, while the latter is cost effective only if the cost of the transpose is amortized over many accesses. I used the second approach to optimize code 10. Code 5 has four-dimensional arrays and loops are nested four deep. For all of the reasons cited above the compiler is not able to restructure three key loops. Assume C arrays and let the four dimensions of the arrays be i, j, k, and l. In the original code, the index structure of the three loops is L1: for i L2: for i L3: for i for l for l for j for k for j for k for j for k for l So only L3 accesses array elements in cache order. L1 is a very complex loop—much too complex to invert. I brought the loop into cache alignment by transposing the second and fourth dimensions of the arrays. Since the code uses a macro to compute all array indexes, I effected the transpose at construction and changed the macro appropriately. The dimensions of the new arrays are now: i, l, k, and j. L3 is a simple loop and easily inverted. L2 has a loop-carried scalar dependence in k. By promoting the scalar name that carries the dependence to an array, I was able to invert the third and fourth subloops aligning the loop with cache. Code 5 is by far the most difficult of the four codes to optimize for array accesses; but the knowledge required to fix the problems is no more than that required for the other codes. I would judge this code at the limits of, but not beyond, the capabilities of appropriately trained computational scientists. Array Strides When a cache miss occurs, a line (64 bytes) rather than just one word is loaded into the cache. If data is accessed stride 1, than the cost of the miss is amortized over 8 words. Any stride other than one reduces the cost savings. Two of the ten codes studied suffered from non-unit strides. The codes represent two important classes of "strided" codes. Code 1 employs a multi-grid algorithm to reduce time to convergence. The grids are every tenth, fifth, second, and unit element. Since time to convergence is inversely proportional to the distance between elements, coarse grids converge quickly providing good starting values for finer grids. The better starting values further reduce the time to convergence. The downside is that grids of every nth element, n > 1, introduce non-unit strides into the computation. In the original code, much of the savings of the multi-grid algorithm were lost due to this problem. I eliminated the problem by compressing (copying) coarse grids into continuous memory, and rewriting the computation as a function of the compressed grid. On convergence, I copied the final values of the compressed grid back to the original grid. The savings gained from unit stride access of the compressed grid more than paid for the cost of copying. Using compressed grids, the loop from code 1 included in the previous section becomes do j = 1, GZ do i = 1, GZ T1 = CA(i+0, j-1) + CA(i-1, j+0) T4 = CA1(i+1, j+0) + CA1(i+0, j+1) S1 = T1 + T4 - 4 * CA1(i+0, j+0) CA(i+0, j+0) = CA1(i+0, j+0) + DD * S1 enddo enddo where CA and CA1 are compressed arrays of size GZ. Code 7 traverses a list of objects selecting objects for later processing. The labels of the selected objects are stored in an array. The selection step has unit stride, but the processing steps have irregular stride. A fix is to save the parameters of the selected objects in temporary arrays as they are selected, and pass the temporary arrays to the processing functions. The fix is practical if the same parameters are used in selection as in processing, or if processing comprises a series of distinct steps which use overlapping subsets of the parameters. Both conditions are true for code 7, so I achieved significant improvement by copying parameters to temporary arrays during selection. Data reuse In the previous sections, we optimized for spatial locality. It is also important to optimize for temporal locality. Once read, a datum should be used as much as possible before it is forced from cache. Loop fusion and loop unrolling are two techniques that increase temporal locality. Unfortunately, both techniques increase register pressure—as loop bodies become larger, the number of registers required to hold temporary values grows. Once register spilling occurs, any gains evaporate quickly. For multiprocessors with small register sets or small caches, the sweet spot can be very small. In the ten codes presented here, I found no opportunities for loop fusion and only two opportunities for loop unrolling (codes 1 and 3). In code 1, unrolling the outer and inner loop one iteration increases the number of result values computed by the loop body from 1 to 4, do J = 1, GZ-2, 2 do I = 1, GZ-2, 2 T1 = CA1(i+0, j-1) + CA1(i-1, j+0) T2 = CA1(i+1, j-1) + CA1(i+0, j+0) T3 = CA1(i+0, j+0) + CA1(i-1, j+1) T4 = CA1(i+1, j+0) + CA1(i+0, j+1) T5 = CA1(i+2, j+0) + CA1(i+1, j+1) T6 = CA1(i+1, j+1) + CA1(i+0, j+2) T7 = CA1(i+2, j+1) + CA1(i+1, j+2) S1 = T1 + T4 - 4 * CA1(i+0, j+0) S2 = T2 + T5 - 4 * CA1(i+1, j+0) S3 = T3 + T6 - 4 * CA1(i+0, j+1) S4 = T4 + T7 - 4 * CA1(i+1, j+1) CA(i+0, j+0) = CA1(i+0, j+0) + DD * S1 CA(i+1, j+0) = CA1(i+1, j+0) + DD * S2 CA(i+0, j+1) = CA1(i+0, j+1) + DD * S3 CA(i+1, j+1) = CA1(i+1, j+1) + DD * S4 enddo enddo The loop body executes 12 reads, whereas as the rolled loop shown in the previous section executes 20 reads to compute the same four values. In code 3, two loops are unrolled 8 times and one loop is unrolled 4 times. Here is the before for (k = 0; k < NK[u]; k++) { sum = 0.0; for (y = 0; y < NY; y++) { sum += W[y][u][k] * delta[y]; } backprop[i++]=sum; } and after code for (k = 0; k < KK - 8; k+=8) { sum0 = 0.0; sum1 = 0.0; sum2 = 0.0; sum3 = 0.0; sum4 = 0.0; sum5 = 0.0; sum6 = 0.0; sum7 = 0.0; for (y = 0; y < NY; y++) { sum0 += W[y][0][k+0] * delta[y]; sum1 += W[y][0][k+1] * delta[y]; sum2 += W[y][0][k+2] * delta[y]; sum3 += W[y][0][k+3] * delta[y]; sum4 += W[y][0][k+4] * delta[y]; sum5 += W[y][0][k+5] * delta[y]; sum6 += W[y][0][k+6] * delta[y]; sum7 += W[y][0][k+7] * delta[y]; } backprop[k+0] = sum0; backprop[k+1] = sum1; backprop[k+2] = sum2; backprop[k+3] = sum3; backprop[k+4] = sum4; backprop[k+5] = sum5; backprop[k+6] = sum6; backprop[k+7] = sum7; } for one of the loops unrolled 8 times. Optimizing for temporal locality is the most difficult optimization considered in this paper. The concepts are not difficult, but the sweet spot is small. Identifying where the program can benefit from loop unrolling or loop fusion is not trivial. Moreover, it takes some effort to get it right. Still, educating scientific programmers about temporal locality and teaching them how to optimize for it will pay dividends. Reducing instruction count Execution time is a function of instruction count. Reduce the count and you usually reduce the time. The best solution is to use a more efficient algorithm; that is, an algorithm whose order of complexity is smaller, that converges quicker, or is more accurate. Optimizing source code without changing the algorithm yields smaller, but still significant, gains. This paper considers only the latter because the intent is to study how much better codes can run if written by programmers schooled in basic code optimization techniques. The ten codes studied benefited from three types of "instruction reducing" optimizations. The two most prevalent were hoisting invariant memory and data operations out of inner loops. The third was eliminating unnecessary data copying. The nature of these inefficiencies is language dependent. Memory operations The semantics of C make it difficult for the compiler to determine all the invariant memory operations in a loop. The problem is particularly acute for loops in functions since the compiler may not know the values of the function's parameters at every call site when compiling the function. Most compilers support pragmas to help resolve ambiguities; however, these pragmas are not comprehensive and there is no standard syntax. To guarantee that invariant memory operations are not executed repetitively, the user has little choice but to hoist the operations by hand. The problem is not as severe in Fortran programs because in the absence of equivalence statements, it is a violation of the language's semantics for two names to share memory. Codes 3 and 5 are C programs. In both cases, the compiler did not hoist all invariant memory operations from inner loops. Consider the following loop from code 3 for (y = 0; y < NY; y++) { i = 0; for (u = 0; u < NU; u++) { for (k = 0; k < NK[u]; k++) { dW[y][u][k] += delta[y] * I1[i++]; } } } Since dW[y][u] can point to the same memory space as delta for one or more values of y and u, assignment to dW[y][u][k] may change the value of delta[y]. In reality, dW and delta do not overlap in memory, so I rewrote the loop as for (y = 0; y < NY; y++) { i = 0; Dy = delta[y]; for (u = 0; u < NU; u++) { for (k = 0; k < NK[u]; k++) { dW[y][u][k] += Dy * I1[i++]; } } } Failure to hoist invariant memory operations may be due to complex address calculations. If the compiler can not determine that the address calculation is invariant, then it can hoist neither the calculation nor the associated memory operations. As noted above, code 5 uses a macro to address four-dimensional arrays #define MAT4D(a,q,i,j,k) (double *)((a)->data + (q)*(a)->strides[0] + (i)*(a)->strides[3] + (j)*(a)->strides[2] + (k)*(a)->strides[1]) The macro is too complex for the compiler to understand and so, it does not identify any subexpressions as loop invariant. The simplest way to eliminate the address calculation from the innermost loop (over i) is to define a0 = MAT4D(a,q,0,j,k) before the loop and then replace all instances of *MAT4D(a,q,i,j,k) in the loop with a0[i] A similar problem appears in code 6, a Fortran program. The key loop in this program is do n1 = 1, nh nx1 = (n1 - 1) / nz + 1 nz1 = n1 - nz * (nx1 - 1) do n2 = 1, nh nx2 = (n2 - 1) / nz + 1 nz2 = n2 - nz * (nx2 - 1) ndx = nx2 - nx1 ndy = nz2 - nz1 gxx = grn(1,ndx,ndy) gyy = grn(2,ndx,ndy) gxy = grn(3,ndx,ndy) balance(n1,1) = balance(n1,1) + (force(n2,1) * gxx + force(n2,2) * gxy) * h1 balance(n1,2) = balance(n1,2) + (force(n2,1) * gxy + force(n2,2) * gyy)*h1 end do end do The programmer has written this loop well—there are no loop invariant operations with respect to n1 and n2. However, the loop resides within an iterative loop over time and the index calculations are independent with respect to time. Trading space for time, I precomputed the index values prior to the entering the time loop and stored the values in two arrays. I then replaced the index calculations with reads of the arrays. Data operations Ways to reduce data operations can appear in many forms. Implementing a more efficient algorithm produces the biggest gains. The closest I came to an algorithm change was in code 4. This code computes the inner product of K-vectors A(i) and B(j), 0 = i < N, 0 = j < M, for most values of i and j. Since the program computes most of the NM possible inner products, it is more efficient to compute all the inner products in one triply-nested loop rather than one at a time when needed. The savings accrue from reading A(i) once for all B(j) vectors and from loop unrolling. for (i = 0; i < N; i+=8) { for (j = 0; j < M; j++) { sum0 = 0.0; sum1 = 0.0; sum2 = 0.0; sum3 = 0.0; sum4 = 0.0; sum5 = 0.0; sum6 = 0.0; sum7 = 0.0; for (k = 0; k < K; k++) { sum0 += A[i+0][k] * B[j][k]; sum1 += A[i+1][k] * B[j][k]; sum2 += A[i+2][k] * B[j][k]; sum3 += A[i+3][k] * B[j][k]; sum4 += A[i+4][k] * B[j][k]; sum5 += A[i+5][k] * B[j][k]; sum6 += A[i+6][k] * B[j][k]; sum7 += A[i+7][k] * B[j][k]; } C[i+0][j] = sum0; C[i+1][j] = sum1; C[i+2][j] = sum2; C[i+3][j] = sum3; C[i+4][j] = sum4; C[i+5][j] = sum5; C[i+6][j] = sum6; C[i+7][j] = sum7; }} This change requires knowledge of a typical run; i.e., that most inner products are computed. The reasons for the change, however, derive from basic optimization concepts. It is the type of change easily made at development time by a knowledgeable programmer. In code 5, we have the data version of the index optimization in code 6. Here a very expensive computation is a function of the loop indices and so cannot be hoisted out of the loop; however, the computation is invariant with respect to an outer iterative loop over time. We can compute its value for each iteration of the computation loop prior to entering the time loop and save the values in an array. The increase in memory required to store the values is small in comparison to the large savings in time. The main loop in Code 8 is doubly nested. The inner loop includes a series of guarded computations; some are a function of the inner loop index but not the outer loop index while others are a function of the outer loop index but not the inner loop index for (j = 0; j < N; j++) { for (i = 0; i < M; i++) { r = i * hrmax; R = A[j]; temp = (PRM[3] == 0.0) ? 1.0 : pow(r, PRM[3]); high = temp * kcoeff * B[j] * PRM[2] * PRM[4]; low = high * PRM[6] * PRM[6] / (1.0 + pow(PRM[4] * PRM[6], 2.0)); kap = (R > PRM[6]) ? high * R * R / (1.0 + pow(PRM[4]*r, 2.0) : low * pow(R/PRM[6], PRM[5]); < rest of loop omitted > }} Note that the value of temp is invariant to j. Thus, we can hoist the computation for temp out of the loop and save its values in an array. for (i = 0; i < M; i++) { r = i * hrmax; TEMP[i] = pow(r, PRM[3]); } [N.B. – the case for PRM[3] = 0 is omitted and will be reintroduced later.] We now hoist out of the inner loop the computations invariant to i. Since the conditional guarding the value of kap is invariant to i, it behooves us to hoist the computation out of the inner loop, thereby executing the guard once rather than M times. The final version of the code is for (j = 0; j < N; j++) { R = rig[j] / 1000.; tmp1 = kcoeff * par[2] * beta[j] * par[4]; tmp2 = 1.0 + (par[4] * par[4] * par[6] * par[6]); tmp3 = 1.0 + (par[4] * par[4] * R * R); tmp4 = par[6] * par[6] / tmp2; tmp5 = R * R / tmp3; tmp6 = pow(R / par[6], par[5]); if ((par[3] == 0.0) && (R > par[6])) { for (i = 1; i <= imax1; i++) KAP[i] = tmp1 * tmp5; } else if ((par[3] == 0.0) && (R <= par[6])) { for (i = 1; i <= imax1; i++) KAP[i] = tmp1 * tmp4 * tmp6; } else if ((par[3] != 0.0) && (R > par[6])) { for (i = 1; i <= imax1; i++) KAP[i] = tmp1 * TEMP[i] * tmp5; } else if ((par[3] != 0.0) && (R <= par[6])) { for (i = 1; i <= imax1; i++) KAP[i] = tmp1 * TEMP[i] * tmp4 * tmp6; } for (i = 0; i < M; i++) { kap = KAP[i]; r = i * hrmax; < rest of loop omitted > } } Maybe not the prettiest piece of code, but certainly much more efficient than the original loop, Copy operations Several programs unnecessarily copy data from one data structure to another. This problem occurs in both Fortran and C programs, although it manifests itself differently in the two languages. Code 1 declares two arrays—one for old values and one for new values. At the end of each iteration, the array of new values is copied to the array of old values to reset the data structures for the next iteration. This problem occurs in Fortran programs not included in this study and in both Fortran 77 and Fortran 90 code. Introducing pointers to the arrays and swapping pointer values is an obvious way to eliminate the copying; but pointers is not a feature that many Fortran programmers know well or are comfortable using. An easy solution not involving pointers is to extend the dimension of the value array by 1 and use the last dimension to differentiate between arrays at different times. For example, if the data space is N x N, declare the array (N, N, 2). Then store the problem’s initial values in (_, _, 2) and define the scalar names new = 2 and old = 1. At the start of each iteration, swap old and new to reset the arrays. The old–new copy problem did not appear in any C program. In programs that had new and old values, the code swapped pointers to reset data structures. Where unnecessary coping did occur is in structure assignment and parameter passing. Structures in C are handled much like scalars. Assignment causes the data space of the right-hand name to be copied to the data space of the left-hand name. Similarly, when a structure is passed to a function, the data space of the actual parameter is copied to the data space of the formal parameter. If the structure is large and the assignment or function call is in an inner loop, then copying costs can grow quite large. While none of the ten programs considered here manifested this problem, it did occur in programs not included in the study. A simple fix is always to refer to structures via pointers. Optimizing loop structures Since scientific programs spend almost all their time in loops, efficient loops are the key to good performance. Conditionals, function calls, little instruction level parallelism, and large numbers of temporary values make it difficult for the compiler to generate tightly packed, highly efficient code. Conditionals and function calls introduce jumps that disrupt code flow. Users should eliminate or isolate conditionls to their own loops as much as possible. Often logical expressions can be substituted for if-then-else statements. For example, code 2 includes the following snippet MaxDelta = 0.0 do J = 1, N do I = 1, M < code omitted > Delta = abs(OldValue ? NewValue) if (Delta > MaxDelta) MaxDelta = Delta enddo enddo if (MaxDelta .gt. 0.001) goto 200 Since the only use of MaxDelta is to control the jump to 200 and all that matters is whether or not it is greater than 0.001, I made MaxDelta a boolean and rewrote the snippet as MaxDelta = .false. do J = 1, N do I = 1, M < code omitted > Delta = abs(OldValue ? NewValue) MaxDelta = MaxDelta .or. (Delta .gt. 0.001) enddo enddo if (MaxDelta) goto 200 thereby, eliminating the conditional expression from the inner loop. A microprocessor can execute many instructions per instruction cycle. Typically, it can execute one or more memory, floating point, integer, and jump operations. To be executed simultaneously, the operations must be independent. Thick loops tend to have more instruction level parallelism than thin loops. Moreover, they reduce memory traffice by maximizing data reuse. Loop unrolling and loop fusion are two techniques to increase the size of loop bodies. Several of the codes studied benefitted from loop unrolling, but none benefitted from loop fusion. This observation is not too surpising since it is the general tendency of programmers to write thick loops. As loops become thicker, the number of temporary values grows, increasing register pressure. If registers spill, then memory traffic increases and code flow is disrupted. A thick loop with many temporary values may execute slower than an equivalent series of thin loops. The biggest gain will be achieved if the thick loop can be split into a series of independent loops eliminating the need to write and read temporary arrays. I found such an occasion in code 10 where I split the loop do i = 1, n do j = 1, m A24(j,i)= S24(j,i) * T24(j,i) + S25(j,i) * U25(j,i) B24(j,i)= S24(j,i) * T25(j,i) + S25(j,i) * U24(j,i) A25(j,i)= S24(j,i) * C24(j,i) + S25(j,i) * V24(j,i) B25(j,i)= S24(j,i) * U25(j,i) + S25(j,i) * V25(j,i) C24(j,i)= S26(j,i) * T26(j,i) + S27(j,i) * U26(j,i) D24(j,i)= S26(j,i) * T27(j,i) + S27(j,i) * V26(j,i) C25(j,i)= S27(j,i) * S28(j,i) + S26(j,i) * U28(j,i) D25(j,i)= S27(j,i) * T28(j,i) + S26(j,i) * V28(j,i) end do end do into two disjoint loops do i = 1, n do j = 1, m A24(j,i)= S24(j,i) * T24(j,i) + S25(j,i) * U25(j,i) B24(j,i)= S24(j,i) * T25(j,i) + S25(j,i) * U24(j,i) A25(j,i)= S24(j,i) * C24(j,i) + S25(j,i) * V24(j,i) B25(j,i)= S24(j,i) * U25(j,i) + S25(j,i) * V25(j,i) end do end do do i = 1, n do j = 1, m C24(j,i)= S26(j,i) * T26(j,i) + S27(j,i) * U26(j,i) D24(j,i)= S26(j,i) * T27(j,i) + S27(j,i) * V26(j,i) C25(j,i)= S27(j,i) * S28(j,i) + S26(j,i) * U28(j,i) D25(j,i)= S27(j,i) * T28(j,i) + S26(j,i) * V28(j,i) end do end do Conclusions Over the course of the last year, I have had the opportunity to work with over two dozen academic scientific programmers at leading research universities. Their research interests span a broad range of scientific fields. Except for two programs that relied almost exclusively on library routines (matrix multiply and fast Fourier transform), I was able to improve significantly the single processor performance of all codes. Improvements range from 2x to 15.5x with a simple average of 4.75x. Changes to the source code were at a very high level. I did not use sophisticated techniques or programming tools to discover inefficiencies or effect the changes. Only one code was parallel despite the availability of parallel systems to all developers. Clearly, we have a problem—personal scientific research codes are highly inefficient and not running parallel. The developers are unaware of simple optimization techniques to make programs run faster. They lack education in the art of code optimization and parallel programming. I do not believe we can fix the problem by publishing additional books or training manuals. To date, the developers in questions have not studied the books or manual available, and are unlikely to do so in the future. Short courses are a possible solution, but I believe they are too concentrated to be much use. The general concepts can be taught in a three or four day course, but that is not enough time for students to practice what they learn and acquire the experience to apply and extend the concepts to their codes. Practice is the key to becoming proficient at optimization. I recommend that graduate students be required to take a semester length course in optimization and parallel programming. We would never give someone access to state-of-the-art scientific equipment costing hundreds of thousands of dollars without first requiring them to demonstrate that they know how to use the equipment. Yet the criterion for time on state-of-the-art supercomputers is at most an interesting project. Requestors are never asked to demonstrate that they know how to use the system, or can use the system effectively. A semester course would teach them the required skills. Government agencies that fund academic scientific research pay for most of the computer systems supporting scientific research as well as the development of most personal scientific codes. These agencies should require graduate schools to offer a course in optimization and parallel programming as a requirement for funding. About the Author John Feo received his Ph.D. in Computer Science from The University of Texas at Austin in 1986. After graduate school, Dr. Feo worked at Lawrence Livermore National Laboratory where he was the Group Leader of the Computer Research Group and principal investigator of the Sisal Language Project. In 1997, Dr. Feo joined Tera Computer Company where he was project manager for the MTA, and oversaw the programming and evaluation of the MTA at the San Diego Supercomputer Center. In 2000, Dr. Feo joined Sun Microsystems as an HPC application specialist. He works with university research groups to optimize and parallelize scientific codes. Dr. Feo has published over two dozen research articles in the areas of parallel parallel programming, parallel programming languages, and application performance.

  Read the article

< Previous Page | 23 24 25 26 27